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]- ↑ «Complexity Zoo:P - Complexity Zoo» (en anglès). Arxivat de l'original el 2018-01-19. [Consulta: 1r desembre 2018].
- ↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.
| Considerades tractables | |
|---|---|
| Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
