Loading AI tools
Hierarchie von Komplexitätsklassen zwischen P und PSPACE. Aus Wikipedia, der freien Enzyklopädie
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.
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.
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:
Mit Blick auf Komplexitätsklassen ergibt sich die folgende Notation:
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.
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.
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
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. .
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:
Im Falle der Gleichheit von P und NP kollabiert die Polynomialzeithierarchie vollständig, d. h. alle und wären gleich P. Allgemein gilt:
In der deskriptiven Komplexitätstheorie beschreibt die Prädikatenlogik zweiter Stufe die Polynomialzeithierarchie.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.