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

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