Polynomialzeithierarchie

Die Polynomialzeithierarchie (PH, auch: polynomielle Hierarchie) ist die vermutete Struktur von Komplexitätsklassen zwischen NP und PSPACE. Der Grundgedanke hinter der Polynomialzeithierarchie ist die Frage, ob durch die Hinzunahme von Orakeln, die Leistungsfähigkeit einer Turingmaschine gesteigert werden kann.

Orakel sind Erweiterungen einer Turingmaschine. Eine Turingmaschine mit Orakel ${\displaystyle A}${\displaystyle A} (wobei ${\displaystyle A}${\displaystyle A} eine Sprache ist), kann in konstanter Zeit entscheiden, ob ein Wort ${\displaystyle w}${\displaystyle w} zu ${\displaystyle A}${\displaystyle A} gehört oder nicht.

Symbolisch wird eine solche Konstruktion wie folgt dargestellt:

• ${\displaystyle B^{A}}${\displaystyle B^{A}} bedeutet, dass eine Turingmaschine ${\displaystyle M}${\displaystyle M} mit ${\displaystyle L(M)=B}${\displaystyle L(M)=B} ein Orakel ${\displaystyle A}${\displaystyle A} befragt.

Mit Blick auf Komplexitätsklassen ergibt sich die folgende Notation:

• ${\displaystyle {\mbox{P}}^{\mbox{NP}}}${\displaystyle {\mbox{P}}^{\mbox{NP}}} (sprich: "P hoch NP") ist die Menge aller Probleme, die sich von einer Turingmaschine entscheiden lassen, die in Abhängigkeit von der Eingabelänge nur polynomiellen Zeitverbrauch aufweist, zur Lösung jedoch ein Orakel benutzen kann, das in der Lage ist, ein Problem aus NP zu entscheiden.

Die Polynomialzeithierarchie wird mit Hilfe der drei Symbole ${\displaystyle \Delta _{i}}${\displaystyle \Delta _{i}}, ${\displaystyle \Sigma _{i}}${\displaystyle \Sigma _{i}} und ${\displaystyle \Pi _{i}}${\displaystyle \Pi _{i}} definiert.

Für diese Symbole gilt:

${\displaystyle \Delta _{0}^{\rm {P}}:=\Sigma _{0}^{\rm {P}}:=\Pi _{0}^{\rm {P}}:={\mbox{P}},}${\displaystyle \Delta _{0}^{\rm {P}}:=\Sigma _{0}^{\rm {P}}:=\Pi _{0}^{\rm {P}}:={\mbox{P}},}

wobei P die Menge aller in Polynomialzeit lösbaren Entscheidungsprobleme ist. Für i ≥ 0 definiert man

${\displaystyle \Delta _{i+1}^{\rm {P}}:={\mbox{P}}^{\Sigma _{i}^{\rm {P}}}}${\displaystyle \Delta _{i+1}^{\rm {P}}:={\mbox{P}}^{\Sigma _{i}^{\rm {P}}}}

${\displaystyle \Sigma _{i+1}^{\rm {P}}:={\mbox{NP}}^{\Pi _{i}^{\rm {P}}}}${\displaystyle \Sigma _{i+1}^{\rm {P}}:={\mbox{NP}}^{\Pi _{i}^{\rm {P}}}}

${\displaystyle \Pi _{i+1}^{\rm {P}}:={\mbox{coNP}}^{\Sigma _{i}^{\rm {P}}}}${\displaystyle \Pi _{i+1}^{\rm {P}}:={\mbox{coNP}}^{\Sigma _{i}^{\rm {P}}}}

Es gilt also insbesondere:

${\displaystyle \Sigma _{1}^{\rm {P}}={\mbox{NP}}}${\displaystyle \Sigma _{1}^{\rm {P}}={\mbox{NP}}}

${\displaystyle \Pi _{1}^{\rm {P}}={\mbox{coNP}}}${\displaystyle \Pi _{1}^{\rm {P}}={\mbox{coNP}}}

${\displaystyle \Delta _{2}^{\rm {P}}={\mbox{P}}^{\mbox{NP}}}${\displaystyle \Delta _{2}^{\rm {P}}={\mbox{P}}^{\mbox{NP}}}

Die Vereinigung aller Klassen der Polynomzeithierarchie PH bildet eine Teilmenge von PSPACE:

• ${\displaystyle {\mbox{PH}}:=\bigcup _{i=0}^{\infty }\Delta _{i}^{\rm {P}}\subseteq {\mbox{PSPACE}}}${\displaystyle {\mbox{PH}}:=\bigcup _{i=0}^{\infty }\Delta _{i}^{\rm {P}}\subseteq {\mbox{PSPACE}}}

Es wird allgemein vermutet, dass diese Inklusion echt ist und dass die polynomielle Hierarchie unendlich viele voneinander verschiedene Stufen besitzt, d.h. dass ${\displaystyle \forall i\geq n:\Sigma _{i}^{\rm {P}}\neq \Sigma _{i+1}^{\rm {P}}}${\displaystyle \forall i\geq n:\Sigma _{i}^{\rm {P}}\neq \Sigma _{i+1}^{\rm {P}}} gilt. Falls aber in Wirklichkeit ${\displaystyle {\mbox{PH}}={\mbox{PSPACE}}}${\displaystyle {\mbox{PH}}={\mbox{PSPACE}}} gilt, liegen PSPACE-vollständige Probleme wie TQBF bereits in einem ${\displaystyle \Sigma _{n}^{\rm {P}}}${\displaystyle \Sigma _{n}^{\rm {P}}} und die polynomielle Hierarchie kollabiert, d.h. es gibt ein ${\displaystyle n}${\displaystyle n} mit:

${\displaystyle \forall i\geq n:\Delta _{i}^{\rm {P}}=\Delta _{n}^{\rm {P}}}${\displaystyle \forall i\geq n:\Delta _{i}^{\rm {P}}=\Delta _{n}^{\rm {P}}} (Analog auch für ${\displaystyle \Sigma _{i}}${\displaystyle \Sigma _{i}} und ${\displaystyle \Pi _{i}}${\displaystyle \Pi _{i}})

Im Falle der Gleichheit von P und NP kollabiert die Polynomialzeithierarchie vollständig, d.h. alle ${\displaystyle \Sigma _{n}^{\rm {P}}}${\displaystyle \Sigma _{n}^{\rm {P}}} und ${\displaystyle \Pi _{n}^{\rm {P}}}${\displaystyle \Pi _{n}^{\rm {P}}} wären gleich P. Allgemein gilt:

• Falls für ein ${\displaystyle k\geq 0}${\displaystyle k\geq 0} gilt: ${\displaystyle \Sigma _{k}^{\rm {P}}=\Sigma _{k+1}^{\rm {P}}}${\displaystyle \Sigma _{k}^{\rm {P}}=\Sigma _{k+1}^{\rm {P}}}, so gilt für alle ${\displaystyle i>k}${\displaystyle i>k}: ${\displaystyle \Sigma _{k}^{\rm {P}}=\Sigma _{i}^{\rm {P}}}${\displaystyle \Sigma _{k}^{\rm {P}}=\Sigma _{i}^{\rm {P}}}

In der deskriptiven Komplexitätstheorie beschreibt die Logik zweiter Stufe die Polynomialzeithierarchie.

Michael Sipser: Introduction to the Theory of Computation. 2. Auflage. ISBN 0-534-94728-X. 

• Komplexitätstheorie