PP (Komplexität)

PP in Bezug auf andere probabilistische Komplexitätsklassen (Zpp, RP, Co-RP, BPP, BQP), die verallgemeinern P innerhalb PSPACE. Es ist nicht bekannt, ob eine dieser Einschlüsse streng ist.

Im Komplexitätstheorie, Pp ist die Klasse von Entscheidungsprobleme lösbar durch a Probabilistische Turing -Maschine in Polynomzeitmit einer Fehlerwahrscheinlichkeit von weniger als 1/2 für alle Fälle. Die Abkürzung Pp bezieht sich auf die probabilistische Polynomzeit. Die Komplexitätsklasse wurde definiert^[1] von Gill im Jahr 1977.

Wenn ein Entscheidungsproblem in liegt PpDann gibt es einen Algorithmus dafür, der Münzen umdrehen und zufällige Entscheidungen treffen darf. Es wird garantiert in Polynomzeit laufen. Wenn die Antwort Ja ist, antwortet der Algorithmus mit einer Wahrscheinlichkeit von mehr als 1/2. Wenn die Antwort Nein lautet, antwortet der Algorithmus mit einer Wahrscheinlichkeit von weniger oder gleich 1/2. In praktischerer Hinsicht ist es die Klasse von Problemen, die auf einen festen Maß an Genauigkeit gelöst werden können, indem ein randomisierter Polynom-Zeit-Algorithmus eine ausreichende (aber begrenzte) Häufigkeit ausgeführt wird.

Polynomial gebundene und probabilistische Maschinen werden als charakterisiert als Ppt, was für probabilistische Polynomzeitmaschinen steht.^[2] Diese Charakterisierung von Turing -Maschinen erfordert keine begrenzte Fehlerwahrscheinlichkeit. Somit, Pp ist die Komplexitätsklasse, die alle Probleme enthält, die von einer PPT -Maschine mit einer Fehlerwahrscheinlichkeit von weniger als 1/2 lösbar sind.

Eine alternative Charakterisierung von Pp ist die Reihe von Problemen, die durch a gelöst werden können Nichtdeterministische Turing -Maschine In der Polynomzeit, in der die Akzeptanzbedingung ist, dass eine Mehrheit (mehr als die Hälfte) der Berechnungspfade akzeptiert werden. Aus diesem Grund haben einige Autoren den alternativen Namen vorgeschlagen Mehrheit-P.^[3]

Definition

Eine Sprache L ist in Pp Wenn und nur wenn es eine probabilistische Turing -Maschine gibt M, so dass

• M Läuft für Polynomzeit für alle Eingänge
• Für alle x in L, M Ausgänge 1 mit Wahrscheinlichkeit streng größer als 1/2
• Für alle x nicht in L, M Ausgänge 1 mit einer Wahrscheinlichkeit von weniger als 1/2.

Alternative, Pp kann mit nur deterministischen Turing -Maschinen definiert werden. Eine Sprache L ist in Pp Wenn und nur wenn es ein Polynom gibt p und deterministische Turing -Maschine M, so dass

• M Läuft für Polynomzeit für alle Eingänge
• Für alle x in L, der Bruchteil der Saiten y von Länge p(|x|) was befriedigt M (x, y) = 1 ist streng größer als 1/2
• Für alle x nicht in L, der Bruchteil der Saiten y von Länge p(|x|) was befriedigt M (x, y) = 1 ist kleiner oder gleich 1/2.

In beiden Definitionen kann "weniger oder gleich" in "weniger als" geändert werden (siehe unten), und der Schwellenwert 1/2 kann durch eine feste rationale Zahl in (0,1) ersetzt werden, ohne die Klasse zu ändern.

PP gegen BPP

BPP ist eine Teilmenge von Pp; Es kann als Teilmenge gesehen werden, für die es effiziente probabilistische Algorithmen gibt. Die Unterscheidung ist in der Fehlerwahrscheinlichkeit, die zulässig ist: in BPPEin Algorithmus muss eine korrekte Antwort (Ja oder Nein) geben, wobei die Wahrscheinlichkeit über einige feste Konstante c> 1/2 liegt, wie z. B. 2/3 oder 501/1000. Wenn dies der Fall ist, können wir den Algorithmus mehrmals ausführen und eine Mehrheitsabstimmung abgeben, um eine gewünschte Wahrscheinlichkeit der Korrektheit von weniger als 1 zu erreichen, wobei die Verwendung des Tschernoff gebunden. Diese Anzahl von Wiederholungen nimmt zu, wenn c wird näher bei 1/2, aber es hängt nicht von der Eingangsgröße ab n.

Das Wichtigste ist, dass diese Konstante c darf nicht vom Eingang abhängen. Andererseits a Pp Algorithmus darf so etwas wie folgt tun:

• Auf einer Ja -Instanz können Sie Ja mit Wahrscheinlichkeit 1/2+1/2 ausgebenⁿ, wo n ist die Länge des Eingangs.
• Auf einer NEIN -Instanz Ja mit Wahrscheinlichkeit 1/2 - 1/2 ausgebenⁿ.

Weil diese beiden Wahrscheinlichkeiten so nahe beieinander liegen, besonders für große nAuch wenn wir es viel Male betreiben, ist es sehr schwierig zu sagen, ob wir auf einer Ja -Instanz oder einer Nein -Instanz arbeiten. Der Versuch, ein fest gewünschter Wahrscheinlichkeitsniveau mithilfe einer Mehrheitsstimmung zu erreichen, und die Tschernoff -Grenze erfordert eine Reihe von Wiederholungen, die exponentiell in der n.

PP im Vergleich zu anderen Komplexitätsklassen

Pp inklusive BPPda probabilistische Algorithmen, die in der Definition von beschrieben wurden BPP bilden eine Untergruppe von denen in der Definition von Pp.

Pp dazu zählt Np. Um dies zu beweisen, zeigen wir, dass die NP-Complete Erfüllbarkeit Das Problem gehört zu Pp. Betrachten Sie einen probabilistischen Algorithmus, der bei einer Formel bei F(x₁Anwesendx₂, ...,x_n) wählt eine Zuordnung aus x₁Anwesendx₂, ...,x_n gleichmäßig zufällig. Anschließend prüft der Algorithmus, ob die Zuweisung die Formel erstellt F WAHR. Wenn ja, gibt es ja aus. Andernfalls gibt es mit Wahrscheinlichkeit Ja aus ${\ displayStyle {\ frac {1} {2}}-{\ frac {1} {2^{n+1}}}}$ und nein mit Wahrscheinlichkeit ${\ displayStyle {\ frac {1} {2}}+{\ frac {1} {2^{n+1}}}}$.

Wenn die Formel unbefriedigend ist, gibt der Algorithmus immer mit Wahrscheinlichkeit Ja aus. $oder$. Wenn es eine zufriedenstellende Zuordnung gibt, wird dies zumindest mit der Wahrscheinlichkeit ausgeben$oder 2^{n}}} \ rechts) +1 \ cdot {\ frac {1} {2^{n}}} = {\ frac {1} {2}}+{\ frac {1} {2^{ 2n+1}}}> {\ frac {1} {2}}}$ (Genau 1/2, wenn es eine unbefriedigende Aufgabe ausgewählt hat und 1, wenn sie eine zufriedenstellende Aufgabe ausgewählt hat, was einem Durchschnitt von einer Zahl von mehr als 1/2 gewählt hat). Somit setzt dieser Algorithmus eine Erfüllbarkeit in Pp. Wie Sa ist NP-Complete und wir können alle deterministischen Präfixen präfixen Polynomzeit viele eins Reduktion auf die Pp Algorithmus, Np ist enthalten in Pp. Da Pp wird unter Komplement geschlossen, es beinhaltet auch Co-NP.

Außerdem, Pp inklusive Ma,^[4] was die beiden vorherigen Einschlüsse abbaut.

Pp dazu zählt BQP, die Klasse der Entscheidungsprobleme, die durch effiziente Polynomzeit lösbar sind Quantencomputer. Tatsächlich ist BQP niedrig zum Pp, was bedeutet, dass a Pp Maschine erzielt keinen Vorteil davon, dass sie lösen können BQP Probleme sofort. Die Klasse der Polynomzeit auf Quantencomputern mit Nachwahl, Postbqp, ist gleich Pp^[5] (sehen #Postbqp unter).

Außerdem, Pp inklusive QMA, was Einschlüsse von abbaut Ma und BQP.

Eine Polynomzeit -Turing -Maschine mit einem PP Orakel (P^Pp) kann alle Probleme in lösen PH, das ganze Polynomhierarchie. Dieses Ergebnis wurde durch gezeigt Seinosuke Toda 1989 und ist bekannt als als Todas Satz. Dies ist ein Beweis dafür, wie schwer es ist, Probleme in Pp. Die Klasse #P ist in gewissem Sinne so schwer, seitdem P^#P = P^Pp und deshalb P^#P inklusive PH auch.

Pp streng einbezogen TC⁰, die Klasse der uneingeschränkten Uniform mit konstantem Tiefen, Boolesche Schaltungen mit Mehrheitstore. (Allender 1996, zitiert in Burtschick 1999).

Pp ist enthalten in PSPACE. Dies kann leicht gezeigt werden, indem ein Polynom-Raum-Algorithmus für gezeigt wird Majsat, definiert unten; Versuchen Sie einfach alle Aufgaben und zählen Sie die Anzahl der zufriedenstellenden.

Pp ist nicht enthalten in GRÖSSE(n^k) für jeden k (nachweisen).

Vollständige Probleme und andere Eigenschaften

nicht wie BPP, Pp ist eher eine syntaktische als eine semantische Klasse. Jede Polynomzeit-probabilistische Maschine erkennt eine Sprache in Pp. Angesichts einer Beschreibung einer polynomialen probabilistischen Maschine ist es im Allgemeinen unentscheidbar, festzustellen, ob sie eine Sprache in erkennt BPP.

Pp hat zum Beispiel natürliche vollständige Probleme, Majsat. Majsat ist ein Entscheidungsproblem, bei dem einer eine Boolesche Formel F erhalten wird. Die Antwort muss Ja sein, wenn mehr als die Hälfte aller Aufgaben x₁Anwesendx₂, ...,x_n Machen Sie f wahr und nein sonst.

Beweis, dass PP unter Komplement geschlossen ist

Lassen L eine Sprache sein in Pp. Lassen ${\ displayStyle l^{c}}$ bezeichnen die Ergänzung von L. Durch die Definition von Pp Es gibt einen polynomialen probabilistischen Algorithmus A mit der Eigenschaft das

$oder \ Rightarrow \ pr [a {\ text {akzeptiert}} x] \ leq {\ frac {1} {2}}.}$

Wir behaupten das Ohne Verlust der AllgemeinheitDie letztere Ungleichheit ist immer streng; Der Satz kann aus dieser Behauptung abgeleitet werden: Lassen Sie ${\ displayStyle a^{c}}$ bezeichnen die Maschine, die gleich ist wie A außer dass ${\ displayStyle a^{c}}$ akzeptiert wann A würde ablehnen und umgekehrt. Dann

$oder \ quad x \ nicht \ in l^{c} \ rightarrow \ pr [a^{c} {\ text {akzeptiert}} x] <{\ frac {1} {2}},}$

das impliziert das ${\ displayStyle l^{c}}$ ist in Pp.

Jetzt rechtfertigen wir unsere ohne Verlust der Allgemeingültigkeit. Lassen ${\ displayStyle f (| x |)}$ Sei die Polynom Obergrenze in der Laufzeit von A auf Eingabe x. Daher A macht höchstens ${\ displayStyle f (| x |)}$ Zufällige Münze flippt während seiner Ausführung. Insbesondere die Akzeptanzwahrscheinlichkeit ist ein ganzzahliges Multiple von ${\ displayStyle 2^{-f (| x |)}}$ und wir haben:

${\ displaystyle x \ in l \ rightarrow \ pr [a {\ text {akzeptiert}} x] \ geq {\ frac {1} {2}}+{\ frac {1} {2^{f (| x | )}}}.}$

Definieren Sie eine Maschine A'Wie folgt: auf Eingabe x, A'Läuft A als Unterprogramm und lehnt ab, wenn A würde ablehnen; sonst wenn A würde akzeptieren, A'Flips ${\ displayStyle f (| x |) +1}$ Münzen und ablehnt, wenn sie alle Köpfe sind, und akzeptiert etwas anderes. Dann

$oder {2^{f (| x |) +1}}} \ rechts) <{\ frac {1} {2}} \ quad {\ text {und}} \ quad x \ in l \ rightarrow \ pr [a '{\ text {akzeptiert}} x] \ geq \ links ({\ frac {1} {2}}+{\ frac {1} {2^{f (| x |)}} \ rechts) \ cdot \ links (1-{\ frac {1} {2^{f (| x |) +1}} \ rechts)> {\ frac {1} {2}}.}.}.$

Dies rechtfertigt die Annahme (seitdem A'Ist immer noch ein polynomialer probabilistischer Algorithmus) und vervollständigt den Beweis.

David Russo bewies in seinem Ph.D. These^[6] das Pp ist unter geschlossen Symmetrischer Unterschied. Es war ein Offenes Problem seit 14 Jahren, ob Pp wurde unter geschlossen Union und Überschneidung; Dies wurde von Beigel, Reingold und Spielman im Bejahten.^[7] Alternative Beweise wurden später von Li gegeben^[8] und Aaronson (siehe #Postbqp unter).

Andere äquivalente Komplexitätsklassen

Postbqp

Die Quantenkomplexitätsklasse BQP ist die Klasse von Problemen lösbar in Polynomzeit auf einen Quanten -Turing -Maschine. Beim Hinzufügen Nachwahl, eine größere Klasse genannt Postbqp wird erhalten. Nach der Nachwahl gibt dem Computer informell die folgende Macht: Wenn ein Ereignis (z. B. das Messen eines Qubits in einem bestimmten Zustand), dürfen Sie annehmen, dass er stattfindet.^[9] Scott Aaronson zeigte im Jahr 2004 das Postbqp ist gleich Pp.^[5][10] Diese Neuformulierung von Pp erleichtert es, bestimmte Ergebnisse wie das zu zeigen Pp wird unter Kreuzung (und damit unter Union) geschlossen, das BQP ist niedrig zum Pp, und das QMA ist enthalten in Pp.

PQP

Pp ist auch gleich einer anderen Quantenkomplexitätsklasse, bekannt als als PQP, das ist das unbegrenzte Fehleranalogon von BQP. Es bezeichnet die Klasse von Entscheidungsproblemen, die in Polynomzeit durch einen Quantencomputer lösbar sind, mit einer Fehlerwahrscheinlichkeit von weniger als 1/2 für alle Fälle. Auch wenn alle Amplituden verwendet werden PQP-Computation stammen aus algebraischen Zahlen, immer noch aus PQP fällt zusammen mit Pp.^[11]

Anmerkungen

Verweise

• Papadimitriou, C. (1994). "Kapitel 11". Rechenkomplexität. Addison-Wesley..
• Allender, E. (1996). "Eine Notiz an den unteren Grenzen der gleichmäßigen Schaltung für die Zählhierarchie". Proceedings 2. International Computing and Combinatorics Conference (Cocoon). Vorlesungsnotizen in Informatik. Vol. 1090. Springer-Verlag. S. 127–135..
• Burtschick, Hans-Jörg; Vollmer, Heribert (1999). "Lindström -Quantifizierer und Blattsprachendefinierbarkeit". ECCC TR96-005. {{}}: Journal zitieren erfordert |journal= (Hilfe).

Externe Links

• Komplexitätszoo: Pp