PH (clase de complejidad)

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)

${\displaystyle {\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.

• Datos: Q1063380