Polynomialzeithierarchie

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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-Turingmaschine[Bearbeiten | Quelltext bearbeiten]

Orakel sind Erweiterungen einer Turingmaschine. Eine Turingmaschine mit Orakel (wobei eine Sprache ist), kann in konstanter Zeit 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.

Mathematische Definition[Bearbeiten | Quelltext bearbeiten]

Bildliche Darstellung der Polynomialzeithierarchie. Die Pfeile bezeichnen Eingliederung.

Die Polynomialzeithierarchie wird mit Hilfe der drei Symbole , und definiert.

Für diese Symbole gilt:

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

Es gilt also insbesondere:

In der Literatur findet sich für häufig die alternative Definition . 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.

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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

Weblinks[Bearbeiten | Quelltext bearbeiten]

  • PH. In: Complexity Zoo. (englisch)