Polynomialzeithierarchie

Die Polynomialzeithierarchie (PH) 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

Orakel sind theoretische Erweiterungen einer Turingmaschine. Sie sind in der Lage, Probleme in konstanter Zeit zu entscheiden. Bildhaft kann man sich ein Orakel als black box vorstellen, die von einer Turingmaschine befragt werden kann. Dadurch ist es möglich, schnellere Turingmaschinen zu konstruieren.

Symbolisch wird eine solche Konstruktion wie folgt dargestellt:

• $M_{1}^{M_{2}}$ bedeutet, dass die Maschine $M_{1}$ zur Entscheidung von Problemen die Maschine $M_{2}$ als Orakel verwendet.

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

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

Mathematische Definition

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

Für diese Symbole gilt:

$\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

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

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

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

Eigenschaften

Anders als zunächst vermutet, können sich durch die Polynomialzeithierarchie nicht alle Komplexitätsklassen abbilden lassen. Zwar ist die genaue Struktur der Hierarchie weiterhin unbekannt, jedoch konnte sich bereits folgender Sachverhalt beweisen lassen:

• $\bigcup _{i=0}^{\infty }\Delta _{i}={\mbox{PSPACE}}$

Zudem weiß man, dass im Falle der Gleichheit von P und NP die Polynomialzeithierarchie kollabiert, d.h. es existierte dann ein $i_{0}\in \mathbb {N}$, so dass gilt:

• $\forall i\geq i_{0}:\Delta _{i}=\Delta _{i_{0}}$ (Analog auch für $\Sigma _{i}$ und $\Pi _{i}$)

Literatur

• Michael Sipser: "Introduction to the Theory of Computation", 2. Auflage, 2005