PH (Complexitat)

Enteoria de la complexitat,laclasse 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 Stockmeyerva ser el primer en definir aquesta classe.És un cas especial demàquina de Turing fitada.També es pot definir com el conjunt dellenguatges expressatsperlògica de segon ordre.

Relació amb d'altres classes

Està continguda aP^#P=P^PPi també dinsPSPACE.

PH conté la majoria de classes dins de PSPACE, en particular contéP,NPico-NP.També conté classes probabilístiques comBPPiRP.Tot i això, hi ha evidències que la classeBQPno està dins de PH.

Se sap que P = NPsi i només siP = PH.