PH (clase de complejidad)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
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 clases de complejidad de la jerarquía polinómica. (Tiempo y espacio)

\mbox{PH} = \bigcup_{k\in\mathbb{N}} \Delta_k\mbox{P}

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.