P-complet

En teoria de la complexitat, la classe de complexitat P-complet és el conjunt dels problemes de decisió que, estant a la classe P, altres problemes de P es poden reduir a ell en un temps polinòmic.[1][2]

Es pot veure aquesta classe com el conjunt de problemes de P que probablement no es poden resoldre eficientment per un computador paral·lel.

El problema més bàsic que pertany a P-complet és el següent: donada una màquina de Turing, una entrada i un enter T en notació unària, determinar si la màquina es para en els primers T passos.

Relació amb d'altres classes

[modifica]

D'igual manera que la classe NP-complet s'utilitza per analitzar la qüestió P = NP, la classe P-complet s'ha usat per estudiar la qüestió NC = P, que segueix oberta, tot i que se sospita que no és certa. Si es trobes un mètode de paral·lelitzar la solució d'algun dels problemes P-complet, indicaria que, efectivament NC = P. L'analogia ve perquè si es trobés una solució en temps polinòmic pels problemes NP-complet, es provaria que P = NP.

Hi ha problemes que no s'han pogut classificar dins de la classe NC o de P-complet, com el de trobar el més gran comú divisor de dos.

Referències

[modifica]
  1. ↑ «Complexity Zoo:P - Complexity Zoo» (en anglès). Arxivat de l'original el 2018-01-19. [Consulta: 1r desembre 2018].
  2. ↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.