PH (Komplexität) - PH (complexity)

In der rechnerischen Komplexitätstheorie ist die Komplexitätsklasse PH die Vereinigung aller Komplexitätsklassen in der polynomiellen Hierarchie :

${\displaystyle \mathrm{PH} =\bigcup_{k\in\mathbb{N}}\Delta_{k}^{\mathrm{P}}}$

PH wurde erstmals von Larry Stockmeyer definiert . Es ist ein Sonderfall der Hierarchie einer beschränkten alternierenden Turingmaschine . Es ist in P ^#P = P ^PP (nach dem Theorem von Toda ; die Klasse von Problemen, die durch eine polynomiale Zeit- Turingmaschine mit Zugriff auf ein #P- oder äquivalent PP- Orakel entscheidbar sind ) und auch in PSPACE enthalten .

PH hat eine einfache logische Charakterisierung : Es ist die Menge von Sprachen, die durch Logik zweiter Ordnung ausdrückbar sind .

PH enthält fast alle bekannten Komplexitätsklassen innerhalb von PSPACE ; insbesondere enthält es P , NP und co-NP . Es enthält sogar probabilistische Klassen wie BPP und RP . Es gibt jedoch Hinweise darauf, dass BQP , die Klasse von Problemen, die von einem Quantencomputer in polynomieller Zeit lösbar sind , nicht in PH enthalten ist .

P = NP genau dann, wenn P = PH . Dies kann einen möglichen Beweis von P ≠ NP vereinfachen , da nur P von der allgemeineren Klasse PH getrennt werden muss .

Verweise

Allgemeine Referenzen

• Bürgisser, Peter (2000). Vollständigkeit und Reduktion in der algebraischen Komplexitätstheorie . Algorithmen und Berechnungen in der Mathematik. 7 . Berlin: Springer-Verlag . s. 66. ISBN 3-540-66752-0. Zbl  0948.68082 .
• Komplexität Zoo : PH