PH (clase de complejidad)

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 P^PP 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.