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 weitern 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma_1^{\rm P}=\mbox{NP}} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Pi_1^{\rm P}=\mbox{coNP}} , und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta_2^{\rm P}=\mbox{P}^{\mbox{NP}}} .

In der Literatur findet sich für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma_i^{\rm P}} häufig die alternative Definition Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma_{i+1}^{\rm P} := \mbox{NP}^{\Sigma_i^{\rm P}}} . Da sich jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma_i^{\rm P}} -Orakel durch Negation der Ausgabe in ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i-1} mal zwischen den beiden Quantifizierungen der Zustände gewechselt wird.

• Die Klasse Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} ist in der Komplexitätsklasse Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma_{i}^{\rm P}} wenn sie mittels

• einer Turingmaschine Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} die in Polynomialzeit arbeitet und
• eines Polynoms Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q}

wie folgt charakterisiert werden kann

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_i} für gerade Indizes ein Allquantor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \forall} und für ungerade Indizes ein Existenzquantor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \exists} ist.

Die Klasse Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Pi_{i}^{\rm P}} besteht aus den Sprachen deren Komplementsprache in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma_{i}^{\rm P}} ist, d. h. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Pi_{i}^{\rm P} = \mbox{co}\Sigma_{i}^{\rm P}} .

Eigenschaften

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

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \forall i\geq n : \Sigma_i^{\rm P} \neq \Sigma_{i+1}^{\rm P}} gilt. Falls aber in Wirklichkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mbox{PH}=\mbox{PSPACE}} gilt, liegen PSPACE-vollständige Probleme wie TQBF bereits in einem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma_n^{\rm{P}}} und die polynomielle Hierarchie kollabiert, d. h. es gibt ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} mit:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \forall i\geq n : \Delta_i^{\rm P} = \Delta_n^{\rm P}} (Analog auch für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma_i} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Pi_i} )

Im Falle der Gleichheit von P und NP kollabiert die Polynomialzeithierarchie vollständig, d. h. alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma_n^{\rm{P}}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Pi_n^{\rm{P}}} wären gleich P. Allgemein gilt:

• Falls für ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k\geq 0} gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma_k^{\rm{P}}=\Sigma_{k+1}^{\rm{P}}} , so gilt für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i > k} : Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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)