PH (Complexitat)

En teoria de la complexitat, la classe de complexitat PH és la unió de totes les classes de complexitat dins la jerarquia polinòmica:

${\mathrm {PH} }=\bigcup _{k\in {\mathbb {N} }}\Delta _{k}^{\mathrm {P} }$

Larry Stockmeyer va ser el primer en definir aquesta classe. És un cas especial de màquina de Turing fitada. També es pot definir com el conjunt de llenguatges expressats per lògica de segon ordre.

Relació amb d'altres classes

Està continguda a P^#P = P^PP i també dins PSPACE.

PH conté la majoria de classes dins de PSPACE, en particular conté P, NP i co-NP. També conté classes probabilístiques com BPP i RP. Tot i això, hi ha evidències que la classe BQP no està dins de PH.

Se sap que P = NP si i només si P = PH.