PP (Komplexität) – Wikipedia

In der Komplexitätstheorie PP ist die Klasse von Entscheidungsproblemen, die von einer probabilistischen Turing-Maschine in Polynomzeit mit einer Fehlerwahrscheinlichkeit von weniger als 1/2 für alle Fälle lösbar sind. Die Abkürzung PP bezieht sich auf die probabilistische Polynomzeit. Die Komplexitätsklasse wurde definiert^[1] von Gill im Jahr 1977.

Wenn ein Entscheidungsproblem vorliegt PPDann gibt es einen Algorithmus dafür, der es erlaubt, Münzen zu werfen und zufällige Entscheidungen zu treffen. Es wird garantiert in Polynomzeit ausgeführt. Wenn die Antwort JA lautet, antwortet der Algorithmus mit einer Wahrscheinlichkeit von mehr als 1/2 mit JA. Wenn die Antwort NEIN lautet, antwortet der Algorithmus mit einer Wahrscheinlichkeit von weniger als oder gleich 1/2 mit JA. In der Praxis ist es die Klasse von Problemen, die mit einem festgelegten Grad an Genauigkeit gelöst werden kann, indem ein randomisierter Polynom-Zeit-Algorithmus ausreichend (aber begrenzt) oft ausgeführt wird.

Polynomgebundene und probabilistische Turingmaschinen sind gekennzeichnet als PPT, was für probabilistische Polynomzeitmaschinen steht.^[2] Diese Charakterisierung von Turingmaschinen erfordert keine begrenzte Fehlerwahrscheinlichkeit. Daher, PP ist die Komplexitätsklasse, die alle Probleme enthält, die von einer PPT-Maschine mit einer Fehlerwahrscheinlichkeit von weniger als 1/2 gelöst werden können.

Eine alternative Charakterisierung von PP ist die Menge von Problemen, die von einer nichtdeterministischen Turing-Maschine in Polynomzeit gelöst werden können, wobei die Akzeptanzbedingung darin besteht, dass eine Mehrheit (mehr als die Hälfte) der Berechnungspfade akzeptiert. Aus diesem Grund haben einige Autoren den alternativen Namen vorgeschlagen Mehrheit-P.^[3]

Definition[edit]

Eine Sprache L. ist in PP genau dann, wenn es eine probabilistische Turingmaschine gibt M., so dass

• M. Läuft für die Polynomzeit an allen Eingängen
• Für alle x im L., M. gibt 1 mit einer Wahrscheinlichkeit aus, die streng größer als 1/2 ist
• Für alle x nicht in L., M. gibt 1 mit einer Wahrscheinlichkeit kleiner oder gleich 1/2 aus.

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

• M. Läuft für die Polynomzeit an allen Eingängen
• Für alle x im L., der Bruchteil der Saiten y von Länge p(|x|) die befriedigen 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|) die befriedigen M (x, y) = 1 ist kleiner oder gleich 1/2.

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

PP gegen BPP[edit]

BPP ist eine Teilmenge von PP;; Es kann als Teilmenge angesehen werden, für die es effiziente probabilistische Algorithmen gibt. Die Unterscheidung liegt in der zulässigen Fehlerwahrscheinlichkeit: in BPPmuss ein Algorithmus eine korrekte Antwort (JA oder NEIN) mit einer Wahrscheinlichkeit geben, die eine feste Konstante c> 1/2 überschreitet, wie z. B. 2/3 oder 501/1000. Wenn dies der Fall ist, können wir den Algorithmus mehrmals ausführen und eine Mehrheitsentscheidung treffen, um eine gewünschte Wahrscheinlichkeit der Korrektheit von weniger als 1 unter Verwendung der Chernoff-Grenze zu erreichen. Diese Anzahl von Wiederholungen erhöht sich, wenn c wird näher an 1, hängt jedoch nicht von der Eingabegröße ab n.

Wichtig ist, dass diese Konstante c darf nicht von der Eingabe abhängen. Auf der anderen Seite a PP Der Algorithmus darf Folgendes tun:

• Geben Sie in einer YES-Instanz YES mit der Wahrscheinlichkeit 1/2 + 1/2 ausⁿ, wo n ist die Länge der Eingabe.
• Geben Sie in einer NEIN-Instanz JA mit der Wahrscheinlichkeit 1/2 – 1/2 ausⁿ.

Weil diese beiden Wahrscheinlichkeiten besonders bei großen so nahe beieinander liegen nSelbst wenn wir es häufig ausführen, ist es sehr schwierig zu sagen, ob wir mit einer YES-Instanz oder einer NO-Instanz arbeiten. Der Versuch, mit fester Mehrheit und der Chernoff-Grenze ein festes gewünschtes Wahrscheinlichkeitsniveau zu erreichen, erfordert eine Reihe von Wiederholungen, die exponentiell sind n.

PP im Vergleich zu anderen Komplexitätsklassen[edit]

PP enthält BPP, da probabilistische Algorithmen in der Definition von BPP bilden eine Teilmenge von denen in der Definition von PP.

PP enthält auch NP. Um dies zu beweisen, zeigen wir, dass das NP-vollständige Erfüllbarkeitsproblem gehört PP. Stellen Sie sich einen probabilistischen Algorithmus vor, der eine gegebene Formel enthält F.((x₁, x₂, …, x_n) wählt eine Aufgabe x₁, x₂, …, x_n gleichmäßig zufällig. Dann prüft der Algorithmus, ob die Zuordnung die Formel ergibt F. wahr. Wenn ja, wird JA ausgegeben. Andernfalls wird mit Wahrscheinlichkeit JA ausgegeben

12– –12n+1{ displaystyle { frac {1} {2}} – { frac {1} {2 ^ {n + 1}}}

und NEIN mit Wahrscheinlichkeit

12+12n+1{ displaystyle { frac {1} {2}} + { frac {1} {2 ^ {n + 1}}}

.

Wenn die Formel nicht zufriedenstellend ist, gibt der Algorithmus immer mit Wahrscheinlichkeit JA aus

12– –12n+1<12{ displaystyle { frac {1} {2}} – { frac {1} {2 ^ {n + 1}}}

. Wenn eine zufriedenstellende Zuordnung vorliegt, wird mindestens mit Wahrscheinlichkeit JA ausgegeben

((12– –12n+1)⋅((1– –12n)+1⋅12n=12+122n+1>12{ displaystyle left ({ frac {1} {2}} – { frac {1} {2 ^ {n + 1}}} right) cdot left (1 – { frac {1} { 2 ^ {n}}} right) +1 cdot { frac {1} {2 ^ {n}}} = { frac {1} {2}} + { frac {1} {2 ^ { 2n + 1}}}> { frac {1} {2}}}

[4] welches die vorherigen zwei Einschlüsse zusammenfasst.

PP enthält auch BQP, die Klasse von Entscheidungsproblemen, die durch effiziente Polynomzeit-Quantencomputer lösbar sind. In der Tat ist BQP niedrig für PPwas bedeutet, dass a PP Maschine erzielt keinen Nutzen aus der Fähigkeit zu lösen BQP Probleme sofort. Die Klasse der Polynomzeit auf Quantencomputern mit Nachauswahl, PostBQP, entspricht PP^[5] (siehe #PostBQP unten).

Außerdem, PP enthält QMA, die Einschlüsse von MA und BQP.

Eine Polynomzeit-Turingmaschine mit einem PP-Orakel (P.^PP) kann alle Probleme in lösen PH, die gesamte Polynomhierarchie. Dieses Ergebnis wurde 1989 von Seinosuke Toda gezeigt und ist als Todas Theorem bekannt. Dies ist ein Beweis dafür, wie schwierig es ist, Probleme zu lösen PP. Die Klasse #P ist in gewissem Sinne ungefähr so ​​schwer, da P.^#P = P.^PP und deshalb P.^#P enthält PH auch.

PP enthält streng TC⁰, die Klasse der einheitlichen booleschen Schaltkreise mit konstanter Tiefe und unbegrenztem Fan-In mit Mehrheitstoren. (Allender 1996, zitiert in Burtschick 1999).

PP ist enthalten in PSPACE. Dies kann leicht gezeigt werden, indem ein Polynomraumalgorithmus für gezeigt wird MAJSAT, unten definiert; Probieren Sie einfach alle Aufgaben aus und zählen Sie die Anzahl der zufriedenstellenden.

PP ist nicht enthalten in GRÖSSE(n^k) für jedes k (Beweis).

Komplette Probleme und andere Eigenschaften[edit]

nicht wie BPP, PP ist eher eine syntaktische als eine semantische Klasse. Jede probabilistische Maschine mit Polynomzeit erkennt eine Sprache in PP. Im Gegensatz dazu ist es bei einer Beschreibung einer Polynom-Zeit-Wahrscheinlichkeitsmaschine im Allgemeinen unentscheidbar, festzustellen, ob sie eine Sprache in erkennt BPP.

PP hat natürlich vollständige Probleme, zum Beispiel MAJSAT. MAJSAT ist ein Entscheidungsproblem, bei dem man eine Boolesche Formel F erhält. Die Antwort muss JA sein, wenn mehr als die Hälfte aller Aufgaben x₁, x₂, …, x_n mache F wahr und NEIN sonst.

Beweis, dass PP unter Ergänzung geschlossen ist[edit]

Lassen L. eine Sprache sein in PP. Lassen

L.c{ displaystyle L ^ {c}}

bezeichnen das Komplement von L.. Nach der Definition von PP Es gibt einen probabilistischen Polynom-Zeit-Algorithmus EIN mit der Eigenschaft, dass

x∈L.⇒Pr[A accepts x]>12undx∉L.⇒Pr[A accepts x]≤12.{ displaystyle x in L Rightarrow Pr[A{text{ accepts }}x]> { frac {1} {2}} quad { text {und}} quad x not in L Rightarrow Pr[A{text{ accepts }}x] leq { frac {1} {2}}.}

EINc{ displaystyle A ^ {c}}

bezeichnen die Maschine, die die gleiche ist wie EIN außer dass EINc{ displaystyle A ^ {c}}

akzeptiert wann EIN würde ablehnen und umgekehrt. Dann

x∈L.c⇒Pr[Ac accepts x]>12undx∉L.c⇒Pr[Ac accepts x]<12,{ displaystyle x in L ^ {c} Rightarrow Pr[A^{c}{text{ accepts }}x]> { frac {1} {2}} quad { text {und}} quad x not in L ^ {c} Rightarrow Pr[A^{c}{text{ accepts }}x]

was impliziert, dass

L.c{ displaystyle L ^ {c}}

ist in PP.

Jetzt begründen wir unsere Annahme ohne Verlust der Allgemeinheit. Lassen

f((|x|){ displaystyle f (| x |)}

sei die Polynomobergrenze für die Laufzeit von EIN bei Eingabe x. So EIN macht höchstens

f((|x|){ displaystyle f (| x |)}

zufällige Münzwürfe während der Ausführung. Insbesondere ist die Akzeptanzwahrscheinlichkeit ein ganzzahliges Vielfaches von

2– –f((|x|){ displaystyle 2 ^ {- f (| x |)}}

und wir haben:

x∈L.⇒Pr[A accepts x]≥12+12f((|x|).{ displaystyle x in L Rightarrow Pr[A{text{ accepts }}x] geq { frac {1} {2}} + { frac {1} {2 ^ {f (| x |)}}.}

Maschine definieren EIN‘Wie folgt: bei Eingabe x, EIN‘Läuft EIN als Unterprogramm und lehnt if ab EIN würde ablehnen; sonst wenn EIN würde akzeptieren, EIN‘Flippt

f((|x|)+1{ displaystyle f (| x |) +1}

Münzen und lehnt ab, wenn sie alle Köpfe sind, und akzeptiert etwas anderes. Dann

x∉L.⇒Pr[A′ accepts x]≤12⋅((1– –12f((|x|)+1)<12undx∈L.⇒Pr[A′ accepts x]≥((12+12f((|x|))⋅((1– –12f((|x|)+1)>12.{ displaystyle x not in L Rightarrow Pr[A'{text{ accepts }}x] leq { frac {1} {2}} cdot left (1 – { frac {1} {2 ^ {f (| x |) +1}}} right){ frac {1} {2}}.}

[6] Das PP ist unter symmetrischer Differenz geschlossen. Es war 14 Jahre lang ein offenes Problem, ob PP wurde unter Vereinigung und Kreuzung geschlossen; Dies wurde von Beigel, Reingold und Spielman bejaht.^[7] Alternative Beweise wurden später von Li gegeben^[8] und Aaronson (siehe #PostBQP unten).

Andere äquivalente Komplexitätsklassen[edit]

PostBQP[edit]

Die Quantenkomplexitätsklasse BQP ist die Klasse von Problemen, die in Polynomzeit auf einer Quanten-Turing-Maschine lösbar sind. Durch Hinzufügen der Nachauswahl wird eine größere Klasse aufgerufen PostBQP erhalten wird. Informell gibt die Nachauswahl dem Computer die folgende Leistung: Wenn ein Ereignis (z. B. das Messen eines Qubits in einem bestimmten Zustand) eine Wahrscheinlichkeit ungleich Null aufweist, können Sie davon ausgehen, dass es stattfindet.^[9]Scott Aaronson hat das 2004 gezeigt PostBQP entspricht PP.^[5][10] Diese Neuformulierung von PP erleichtert das Anzeigen bestimmter Ergebnisse, z PP ist unter Kreuzung (und damit unter Vereinigung) geschlossen, dass BQP ist niedrig für PP, und das QMA ist enthalten in PP.

PQP[edit]

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

1. ^ Gill, John (1977). “Rechenkomplexität probabilistischer Turingmaschinen”. SIAM Journal on Computing. 6 (4): 675–695. doi:10.1137 / 0206049.
2. ^ Lindell, Yehuda; Katz, Jonathan (2015). Einführung in die moderne Kryptographie (2. Aufl.). Chapman und Hall / CRC. p. 46. ​​ISBN 978-1-4665-7027-6.
3. ^ Lance Fortnow. Computerkomplexität: Mittwoch, 4. September 2002: Komplexitätsklasse der Woche: PP. http://weblog.fortnow.com/2002/09/complexity-class-of-week-pp.html
4. ^ NK Vereshchagin, “Auf die Kraft von PP”
5. ^ ^{ein b} Aaronson, Scott (2005). “Quantencomputer, Nachselektion und probabilistische Polynomzeit”. Verfahren der Royal Society A.. 461 (2063): 3473–3482. arXiv:quant-ph / 0412187. Bibcode:2005RSPSA.461.3473A. doi:10.1098 / rspa.2005.1546.
6. ^ David Russo (1985). Strukturelle Eigenschaften von Komplexitätsklassen (Doktorarbeit). Universität von Kalifornien, Santa Barbara.
7. ^ R. Beigel, N. Reingold und DA Spielman, “PP ist unter Kreuzung geschlossen“, Proceedings of ACM Symposium on Theory of Computing 1991S. 1–9, 1991.
8. ^ Lide Li (1993). Auf den Zählfunktionen (Doktorarbeit). Universität von Chicago.
9. ^ Aaronson, Scott. “Die erstaunliche Kraft der Nachauswahl”. Abgerufen 2009-07-27.
10. ^ Aaronson, Scott (11.01.2004). “Komplexitätsklasse der Woche: PP”. Computational Complexity Weblog. Abgerufen 2008-05-02.
11. ^ Yamakami, Tomoyuki (1999). “Analyse von Quantenfunktionen”. Int. J. gefunden. Comput. Sci. 14 (5): 815–852. arXiv:quant-ph / 9909012. Bibcode:1999quant.ph..9012Y.

Verweise[edit]

• Papadimitriou, C. (1994). “Kapitel 11”. Rechenkomplexität. Addison-Wesley..
• Allender, E. (1996). “Ein Hinweis zu den unteren Grenzen der einheitlichen Schaltung für die Zählhierarchie”. Proceedings 2. Internationale Konferenz für Computer und Kombinatorik (COCOON). Vorlesungsunterlagen in Informatik. 1090. Springer-Verlag. S. 127–135..
• Burtschick, Hans-Jörg; Vollmer, Heribert (1999). “Lindström-Quantifizierer und Definierbarkeit der Blattsprache”. ECCC TR96-005. .

Externe Links[edit]