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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Polynomial_time_hierarchy.svg/250px-Polynomial_time_hierarchy.svg.png)
Die Polynomialzeithierarchie besteht aus den Familien , und von Komplexitätsklassen. Die Klassen , und bilden das -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. . Für Level 1 gilt, dass , , und . 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 (wobei eine Sprache ist) kann mit einem einzelnen Berechnungsschritt entscheiden, ob ein Wort zu gehört oder nicht.
Symbolisch wird eine solche Konstruktion wie folgt dargestellt:
- bedeutet, dass eine Turingmaschine mit ein Orakel befragt.
Mit Blick auf Komplexitätsklassen ergibt sich die folgende Notation:
- (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:
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:
Es gilt also insbesondere , , und .
In der Literatur findet sich für häufig die alternative Definition [1]. Da sich jedes -Orakel durch Negation der Ausgabe in ein -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 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 mal zwischen den beiden Quantifizierungen der Zustände gewechselt wird.
- Die Klasse 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 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 ist in der Komplexitätsklasse wenn sie mittels
- einer Turingmaschine die in Polynomialzeit arbeitet und
- eines Polynoms
wie folgt charakterisiert werden kann
wobei für gerade Indizes ein Allquantor und für ungerade Indizes ein Existenzquantor ist.
Die Klasse besteht aus den Sprachen deren Komplementsprache in ist, d. h. .
Eigenschaften
Die Vereinigung aller Klassen der Polynomzeithierarchie PH bildet eine Teilmenge von PSPACE:
Es wird allgemein vermutet, dass diese Inklusion echt ist und dass die polynomielle Hierarchie unendlich viele voneinander verschiedene Stufen besitzt, d. h., dass gilt. Falls aber in Wirklichkeit gilt, liegen PSPACE-vollständige Probleme wie TQBF bereits in einem und die polynomielle Hierarchie kollabiert, d. h. es gibt ein mit:
- (Analog auch für und )
Im Falle der Gleichheit von P und NP kollabiert die Polynomialzeithierarchie vollständig, d. h. alle und wären gleich P. Allgemein gilt:
- Falls für ein gilt: , so gilt für alle :
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)