Polynomhierarchie

Im Computerkomplexitätstheorie, das Polynomhierarchie (manchmal genannt das Polynomzeithierarchie) ist ein Hierarchie von Komplexitätsklassen das verallgemeinern die Klassen Np und Co-NP.^[1] Jede Klasse in der Hierarchie ist darin enthalten PSPACE. Die Hierarchie kann mit Verwendung definiert werden Orakelmaschinen oder Wechsel Turing -Maschinen. Es ist ein ressourcenverrücktes Gegenstück zum arithmetische Hierarchie und analytische Hierarchie aus Mathematische Logik. Die Vereinigung der Klassen in der Hierarchie wird bezeichnet PH.

Klassen innerhalb der Hierarchie haben vollständige Probleme (in Bezug auf Polynomzeitreduzierungen) die fragen, ob Quantifizierte Boolesche Formeln Halten Sie für Formeln mit Einschränkungen der Quantifiziererordnung. Es ist bekannt, dass Gleichheit zwischen Klassen auf derselben Ebene oder aufeinanderfolgenden Ebenen in der Hierarchie einen "Zusammenbruch" der Hierarchie auf diese Ebene bedeuten würde.

Definitionen

Es gibt mehrere äquivalente Definitionen der Klassen der Polynomhierarchie.

Oracle Definition

Definieren Sie für die Orakeldefinition der Polynomhierarchie

${\ displaystyle \ delta _ {0}^{\ mathsf {p}}: = \ sigma _ {0}^{\ mathsf {p}}: = \ pi _ {0}^{\ mathsf {p}}: = {\ mathsf {p}},},}$

wo P ist der Satz von Entscheidungsprobleme lösbar in Polynomzeit. Dann für i ≥ 0 definieren

$oder$

$oder$

$oder$

wo ${\ displaystyle {\ mathsf {p}}^{\ rm {a}}}$ ist der Satz von Entscheidungsprobleme lösbar in Polynomzeit durch a Turing Maschine erweitert von an Orakel für ein vollständiges Problem in Klasse A; die Klassen ${\ displaystyle {\ mathsf {np}}^{\ rm {a}}}$ und ${\ displaystyle {\ mathsf {conp}}^{\ rm {a}}}$ sind analog definiert. Zum Beispiel, $oder$, und ${\ displaystyle \ delta _ {2}^{\ mathsf {p}} = {\ mathsf {p^{np}}}}$ ist die Klasse von Problemen, die in der Polynomzeit durch eine deterministische Turing-Maschine mit einem Orakel für ein NP-Complete-Problem lösbar sind.^[2]

Quantifizierte Boolesche Formeln Definition

Für die existenzielle/universelle Definition der Polynomhierarchie lassen Sie L sei a Sprache (d. h. a Entscheidungsproblem, eine Teilmenge von {0,1}^*), Lassen p sei a Polynomund definieren

$oder ^{\ leq p (| x |)} \ rechts) \ Langle x, w \ rangle \ in l \ rechts. \ rechts \},}$

wo ${\ displayStyle \ Langle x, w \ rangle \ in \ {0,1 \}^{*}}$ ist eine Standardcodierung des Paares binärer Strings x und w als einzelne binäre Zeichenfolge. L repräsentiert eine Reihe geordneter Stringspaare, bei denen die erste Zeichenfolge x ist ein Mitglied von ${\ displayStyle \ existiert ^{p} l}$und die zweite Zeichenfolge w ist ein "kurzer" (${\ displayStyle | w | \ leq p (| x |)}$) Zeugnis, das das aussagte x ist ein Mitglied von ${\ displayStyle \ existiert ^{p} l}$. Mit anderen Worten, ${\ displaystyle x \ in \ existiert ^{p} l}$ Wenn und nur wenn es einen Kurzfalls gibt w so dass ${\ displayStyle \ Langle x, W \ rangle \ in l}$. In ähnlicher Weise definieren Sie

$oder ^{\ leq p (| x |)} \ rechts) \ Langle x, w \ rangle \ in l \ rechts. \ rechts \}}$

Beachten Sie, dass De Morgans Gesetze halt: $oder$ und $oder$, wo L^c ist die Ergänzung von L.

Lassen C eine Klasse von Sprachen sein. Erweitern Sie diese Betreiber so, dass sie nach der Definition an ganzen Klassen von Sprachen arbeiten

$oder {\ mathcal {c}} \ right \}}$

$oder {\ mathcal {c}} \ right \}}$

Auch hier halten de Morgans Gesetze: $oder }}}$ und $oder }}}$, wo $oder$.

Die Klassen Np und Co-NP kann definiert werden als ${\ displaystyle {\ mathsf {np}} = \ exists ^{\ mathsf {p}} {\ mathsf {p}}}$, und ${\ displayStyle {\ mathsf {conp}} = \ forall ^{\ mathsf {p}} {\ mathsf {p}}}$, wo P ist die Klasse aller machbaren (Polynomzeit-) lehenden Sprachen. Die Polynomhierarchie kann rekursiv definiert werden als

$oder$

$oder$

$oder$

Beachten Sie, dass ${\ displaystyle {\ mathsf {np}} = \ sigma _ {1}^{\ mathsf {p}}}$, und ${\ displaystyle {\ mathsf {conp}} = \ pi _ {1}^{\ mathsf {p}}}$.

Diese Definition spiegelt die enge Verbindung zwischen der polynomialen Hierarchie und der wider arithmetische Hierarchie, wo R und BETREFFEND Spielrollen analog zu spielen zu P und Np, beziehungsweise. Das analytische Hierarchie ist auch in ähnlicher Weise definiert, um eine Hierarchie von Teilmengen der realen Zahlen zu geben.

Definition der Turing -Maschinen abwechseln

Ein Wechsel Turing Machine ist eine nicht deterministische Turing-Maschine mit nicht-finalen Zuständen, die in existenzielle und universelle Zustände aufgeteilt sind. Es wird schließlich aus seiner aktuellen Konfiguration akzeptiert, wenn: Sie sich in einem existenziellen Zustand befindet, und kann in einige letztendlich die Konfiguration übergehen. Oder es befindet sich in einem universellen Zustand und jeder Übergang ist ein gewisser Konfiguration. Oder es ist in einem akzeptierenden Zustand.^[3]

Wir definieren ${\ displaystyle \ sigma _ {k}^{\ mathsf {p}}}$ Um die Klasse von Sprachen zu sein, die von einer abwechselnden Turing -Maschine in Polynomzeit akzeptiert werden, so dass der Anfangszustand ein existenzieller Zustand ist und jeder Weg, den die Maschine höchsten k - 1 -mal zwischen existenziellen und universellen Zuständen. Wir definieren ${\ displaystyle \ pi _ {k}^{\ mathsf {p}}}$ In ähnlicher Weise, außer dass der Anfangszustand ein universeller Zustand ist.^[4]

Wenn wir die Erfordernis von höchstens auslassen k - 1 Swaps zwischen den existenziellen und universellen Zuständen, so dass wir nur verlangen, dass unsere abwechselnde Turing -Maschine in der Polynomzeit läuft, dann haben wir die Definition der Klasse AP, was gleich ist PSPACE.^[5]

Beziehungen zwischen Klassen in der Polynomhierarchie

Kommutativer Diagramm entspricht der Polynomzeithierarchie. Die Pfeile bezeichnen Inklusion.

Die Vereinigung aller Klassen in der Polynomhierarchie ist die Komplexitätsklasse PH.

Die Definitionen implizieren die Beziehungen:

$oder P}}}$

$oder P}}}$

$oder$

Im Gegensatz zu den arithmetischen und analytischen Hierarchien, deren Einschlüsse bekannt sind, ist es eine offene Frage, ob eine dieser Einschlüsse angemessen ist, obwohl allgemein angenommen wird, dass sie alle sind. Wenn überhaupt $oder$oder falls vorhanden $oder$dann die Hierarchie bricht auf Level k zusammen: für alle ${\ displayStyle i> k}$, $oder$.^[6] Insbesondere haben wir die folgenden Auswirkungen auf ungelöste Probleme:

• P = Np dann und nur dann, wenn P = PH.^[7]
• Wenn Np = Co-NP dann Np = PH. (Co-NP ist ${\ displaystyle \ pi _ {1}^{\ mathsf {p}}}$.))

Der Fall, in dem Np = PH wird auch als als bezeichnet Zusammenbruch des PH zu die zweite Ebene. Der Fall P = Np entspricht einem Zusammenbruch von PH zu P.

Die Frage des Zusammenbruchs in die erste Ebene wird im Allgemeinen als äußerst schwierig angesehen. Die meisten Forscher glauben nicht an einen Zusammenbruch, selbst bis zur zweiten Ebene.

Beziehungen zu anderen Klassen

Die Polynomhierarchie ist ein Analogon (bei viel geringer Komplexität) der Exponentielle Hierarchie und arithmetische Hierarchie.

Es ist bekannt, dass der pH -Wert darin enthalten ist PSPACE, aber es ist nicht bekannt, ob die beiden Klassen gleich sind. Eine nützliche Umformulierung dieses Problems ist, dass pH = PSPACE, wenn und nur wenn Logik zweiter Ordnung über endliche Strukturen Gewinne keine zusätzliche Leistung von der Zugabe von a Transitive Schließung Operator.

Wenn die Polynomhierarchie welche hat vollständige Problemedann hat es nur endlich viele unterschiedliche Ebenen. Weil dort sind PSPACE-Complete Probleme, wir wissen, dass die Polynomhierarchie, wenn PSPACE = PH, zusammenbrechen muss, da ein PSPACE-Complete-Problem ein ${\ displaystyle \ sigma _ {k}^{\ mathsf {p}}}$-Complete -Problem für einige k.^[8]

Jede Klasse in der Polynomhierarchie enthält ${\ displayStyle \ leq _ {\ rm {m}}^{\ mathsf {p}}}$-Complete-Probleme (Probleme, die unter Polynomzeit abgeschlossen sind, viele eins Reduktionen). Darüber hinaus ist jede Klasse in der Polynomhierarchie unter geschlossen ${\ displayStyle \ leq _ {\ rm {m}}^{\ mathsf {p}}}$-Reduktionen: Das heißt das für eine Klasse C in der Hierarchie und einer Sprache ${\ displayStyle l \ in {\ mathcal {c}}}$, wenn ${\ displayStyle a \ leq _ {\ rm {m}}^{\ mathsf {p}} l}$, dann ${\ displayStyle a \ in {\ mathcal {c}}}$ auch. Diese beiden Fakten zusammen implizieren das, wenn ${\ displayStyle k_ {i}}$ ist ein vollständiges Problem für ${\ displaystyle \ sigma _ {i}^{\ mathsf {p}}}$, dann $oder$, und $oder$. Zum Beispiel, $oder$. Mit anderen Worten, wenn eine Sprache basierend auf einem Orakel in definiert wird CDann können wir davon ausgehen, dass es auf der Grundlage eines vollständigen Problems definiert ist C. Vollständige Probleme fungieren daher als "Vertreter" der Klasse, für die sie vollständig sind.

Das SIPser -Lautemann -Theorem gibt an, dass die Klasse BPP ist in der zweiten Ebene der Polynomhierarchie enthalten.

Kannans Theorem erklärt das für jeden k, ${\ displayStyle \ sigma _ {2}}$ ist nicht enthalten in GRÖSSE(n^k).

Todas Satz gibt an, dass die Polynomhierarchie in p enthalten ist^#P.

Probleme

Siehe auch

• Nachfolger
• Exponentielle Hierarchie
• Arithmetische Hierarchie

Verweise

Allgemeine Referenzen

1. Arora, Sanjeev; Barak, Boaz (2009). Komplexitätstheorie: ein moderner Ansatz. Cambridge University Press. ISBN 978-0-521-42426-4. Abschnitt 1.4, "Maschinen als Saiten und die universelle Turing -Maschine" und 1.7, "Beweis von Satz 1.9"
2. A. R. Meyer und L. J. Stockmeyer. Das Äquivalenzproblem für reguläre Ausdrücke mit Quadrat erfordert einen exponentiellen Platz. In Proceedings of the 13. IEEE Symposium zum Umschalten und Automata -Theorie, S. 125–129, 1972. Das Papier, das die Polynomhierarchie einführte.
3. L. J. Stockmeyer. Die Polynom-Zeit-Hierarchie. Theoretische Informatik, Vol.3, S. 1–22, 1976.
4. C. Papadimitriou. Rechenkomplexität. Addison-Wesley, 1994. Kapitel 17. Polynomhierarchie, S. 409–438.
5. Michael R. Garey und David S. Johnson (1979). Computer und Unverdaulichkeit: Ein Leitfaden zur Theorie der NP-Vervollständigung. W.H. Freeman. ISBN 0-7167-1045-5. Abschnitt 7.2: Die Polynomhierarchie, S. 161–167.

Zitate