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]

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

Mathematische Definition[Bearbeiten]

Bildliche Darstellung der Polynomialzeithierarchie. Die Pfeile bezeichnen Eingliederung.

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}^{\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}
\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}}. 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.

Eigenschaften[Bearbeiten]

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

  • \mbox{PH} := \bigcup_{i=0}^{\infty} \Delta_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[Bearbeiten]

 Michael Sipser: Introduction to the Theory of Computation. 2. Auflage. ISBN 053494728X.

Weblinks[Bearbeiten]

  • PH. In: Complexity Zoo. (englisch)