PH (clase de complejidad)
De Wikipedia, la enciclopedia libre
-
- Para otros usos del término PH, véase la página de desambiguación.
En teoría de la complejidad computacional, la clase de complejidad PH es la unión de todas las clase de complejidad de la jerarquía polinómica.
PH está contenida en las clases PSPACE y PPP que es la clase de los problemas de decisión que pueden ser resueltos en tiempo polinómico en una máquina de Turing con acceso a un oráculo PP.
| clases de complejidad más importantes |
| L | NL | P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C |
| PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH |
