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.

Definition

Bildliche Darstellung der Polynomialzeithierarchie. Die Pfeile bezeichnen Eingliederung.

Die Polynomialzeithierarchie besteht aus den Familien $(\Delta _{i})_{i\geq 1}$ , $(\Sigma _{i})_{i\geq 1}$ und $(\Pi _{i})_{i\geq 1}$ von Komplexitätsklassen. Die Klassen $\Delta _{i}$ , $\Sigma _{i}$ und $\Pi _{i}$ bilden das $i$ -te Level der Hierarchie. Für Level 0 gilt, dass alle drei Klassen identisch mit der Klasse P (der in Polynomialzeit lösbaren Probleme) sind, d. h. $\Delta _{0}^{\rm {P}}=\Sigma _{0}^{\rm {P}}=\Pi _{0}^{\rm {P}}={\mbox{P}}$ . Für Level 1 gilt, dass $\Delta _{1}^{\rm {P}}={\mbox{P}}$ , $\Sigma _{1}^{\rm {P}}={\mbox{NP}}$ , und $\Pi _{1}^{\rm {P}}={\mbox{coNP}}$ . Die Komplexitätsklassen in der Polynomialzeithierarchie können auf verschiedene äquivalente Arten definiert werden.

Definition mit Orakel-Turingmaschinen

Eine Orakel-Turingmaschine ist eine Erweiterung einer Turingmaschine. Eine Turingmaschine mit Orakel $A$ (wobei $A$ eine Sprache ist) kann mit einem einzelnen Berechnungsschritt entscheiden, ob ein Wort $w$ zu $A$ gehört oder nicht.

Symbolisch wird eine solche Konstruktion wie folgt dargestellt:

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

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.

Die Komplexitätsklassen der Polynomialzeithierarchie sind wie folgt definiert:

Für Level 0 gilt:

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

Die weiteren Klassen der Hierarchie sind induktiv definiert. Dazu werden Orakel-Turingmaschinen, die als Orakel eine Komplexitätsklasse des vorherigen Levels der Hierarchie nutzen, verwendet:

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

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

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

Es gilt also insbesondere $\Sigma _{1}^{\rm {P}}={\mbox{NP}}$ , $\Pi _{1}^{\rm {P}}={\mbox{coNP}}$ , und $\Delta _{2}^{\rm {P}}={\mbox{P}}^{\mbox{NP}}$ .

In der Literatur findet sich für $\Sigma _{i}^{\rm {P}}$ häufig die alternative Definition $\Sigma _{i+1}^{\rm {P}}:={\mbox{NP}}^{\Sigma _{i}^{\rm {P}}}$ ^[1]. Da sich jedes $\Sigma _{i}^{\rm {P}}$ -Orakel durch Negation der Ausgabe in ein $\Pi _{i}^{\rm {P}}$ -Orakel überführen lässt (und umgekehrt), ist diese Definition zur oben gewählten äquivalent.

Definition mit Alternierenden Turingmaschinen

Alternierende Turingmaschinen sind eine Erweiterung von nicht-deterministischen Turingmaschinen, bei der die Zustände der Maschine in existentielle und universelle Zustände unterschieden werden. Eine Berechnung die von einem existentiellen Zustand ausgeht akzeptiert die Eingabe wenn mindestens eine der möglichen Berechnungen akzeptiert und eine Berechnung die von einem universellen Zustand ausgeht akzeptiert nur wenn alle möglichen Berechnungen akzeptieren.

Die Polynomialzeithierarchie kann mit Hilfe von Alternierenden Turingmaschinen wie folgt definiert werden.

Die Klasse $\Sigma _{i}^{\rm {P}}$ enthält die Sprachen die von einer alternierende Turingmaschine in Polynomialzeit entschieden werden können, sodass der Initialzustand existentiell ist und auf jedem möglichen Berechnungspfad nur $i-1$ mal zwischen den beiden Quantifizierungen der Zustände gewechselt wird.

Die Klasse $\Pi _{i}^{\rm {P}}$ enthält die Sprachen die von einer alternierende Turingmaschine in Polynomialzeit entschieden werden können, sodass der Initialzustand universell ist und auf jedem möglichen Berechnungspfad nur $i-1$ mal zwischen den beiden Quantifizierungen der Zustände gewechselt wird.

Definition mit Alternierenden Quantoren und Relationen

Diese Definition bedient sich einer mehrstelligen Relation über Bitvektoren die in Polynomialzeit entschieden werden kann, und alternierender Quantifizierung über diese Bitvektoren. Für jedes Level der Hierarchie wird eine weitere Quantorenalternierung hinzugefügt. Die formale Definition der Komplexitätsklassen ist wie folgt.

Eine Sprache $L$ ist in der Komplexitätsklasse $\Sigma _{i}^{\rm {P}}$ wenn sie mittels

einer Turingmaschine $M$ die in Polynomialzeit arbeitet und
eines Polynoms $q$

wie folgt charakterisiert werden kann

x\in L\Leftrightarrow \exists u_{1}\in \{0,1\}^{q(|x|)}\,\forall u_{2}\in \{0,1\}^{q(|x|)}\dots Q_{i}u_{i}\in \{0,1\}^{q(|x|)}M(x,u_{1},\dots ,u_{i})=1

wobei $Q_{i}$ für gerade Indizes ein Allquantor $\forall$ und für ungerade Indizes ein Existenzquantor $\exists$ ist.

Die Klasse $\Pi _{i}^{\rm {P}}$ besteht aus den Sprachen deren Komplementsprache in $\Sigma _{i}^{\rm {P}}$ ist, d. h. $\Pi _{i}^{\rm {P}}={\mbox{co}}\Sigma _{i}^{\rm {P}}$ .

Eigenschaften

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

${\mbox{PH}}:=\bigcup _{i=0}^{\infty }\Delta _{i}^{\rm {P}}=\bigcup _{i=0}^{\infty }\Sigma _{i}^{\rm {P}}=\bigcup _{i=0}^{\infty }\Pi _{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 $\forall i\geq n:\Sigma _{i}^{\rm {P}}\neq \Sigma _{i+1}^{\rm {P}}$ gilt. Falls aber in Wirklichkeit ${\mbox{PH}}={\mbox{PSPACE}}$ gilt, liegen PSPACE-vollständige Probleme wie TQBF bereits in einem $\Sigma _{n}^{\rm {P}}$ und die polynomielle Hierarchie kollabiert, d. h. es gibt ein $n$ mit:

\forall i\geq n:\Delta _{i}^{\rm {P}}=\Delta _{n}^{\rm {P}}

(Analog auch für

\Sigma _{i}

und

\Pi _{i}

)

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

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

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

Literatur

Michael Sipser: Introduction to the Theory of Computation. 3. Auflage. ISBN 0-534-94728-X, 10.3 Alternation - The polynomial time hierarchy, S. 414.
Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge; New York, ISBN 978-0-521-42426-4, 5. The polynomial hierarchy and alternations (Draft [PDF]).
Christos H.Papadimitriou: Computational Complexity. Addison-Wesley, Reading/Mass, ISBN 978-0-201-53082-7, 17.2 The Polynomial Hierarchy.
Marcus Schaefer, Christopher Umans: Completeness in the Polynomial-Time Hierarchy: A Compendium. In: ACM SIGACT News. Band 33, Nr. 3, September 2002, ISSN 0163-5700, S. 32–49, doi:10.1145/582475.582484.
Marcus Schaefer, Christopher Umans: Completeness in the Polynomial-Time Hierarchy: Part II. In: ACM SIGACT News. Band 33, Nr. 4, Dezember 2002, ISSN 0163-5700, S. 22–36, doi:10.1145/601819.601829.

Weblinks

PH. In: Complexity Zoo. (englisch)

Einzelnachweise

↑ Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov: Complexity and Expressive Power of Logic Programming. In: ACM Comput. Surv. Band 33, Nr. 3, 1. September 2001, ISSN 0360-0300, S. 374–425, doi:10.1145/502807.502810.

[1] Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov: Complexity and Expressive Power of Logic Programming. In: ACM Comput. Surv. Band 33, Nr. 3, 1. September 2001, ISSN 0360-0300, S. 374–425, doi:10.1145/502807.502810.

[1]