BPP (Komplexität)

Im Computerkomplexitätstheorie, ein Zweig der Informatik,, probabilistische Polynomzeit begrenzt (BPP) ist die Klasse von Entscheidungsprobleme lösbar durch a Probabilistische Turing -Maschine in Polynomzeit mit einem Fehler Wahrscheinlichkeit für alle Fälle um 1/3 begrenzt.BPP ist einer der größten praktisch Probleme von Problemen, was die meisten Probleme von Interesse an bedeutet BPP effizient haben Probabilistische Algorithmen Das kann schnell auf echten modernen Maschinen ausgeführt werden. BPP enthält auch PDie Klasse der Probleme, die in der Polynomzeit mit einer deterministischen Maschine lösbar sind, da eine deterministische Maschine ein spezieller Fall einer probabilistischen Maschine ist.

Informell ist ein Problem in BPP Wenn es einen Algorithmus dafür gibt, der die folgenden Eigenschaften hat:

• Es darf Münzen umdrehen und zufällige Entscheidungen treffen
• Es wird garantiert in Polynomzeit laufen
• Bei einem bestimmten Lauf des Algorithmus hat es eine Wahrscheinlichkeit, dass höchst 1/3 die falsche Antwort gegeben wird, ob die Antwort Ja oder Nein lautet.

Definition

Eine Sprache L ist in BPP Wenn und nur wenn es vorhanden ist a Probabilistische Turing -Maschine 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 größer oder gleich 2/3
• Für alle x nicht in L, M Ausgänge 1 mit Wahrscheinlichkeit von weniger oder gleich 1/3

Im Gegensatz zur Komplexitätsklasse Zpp, Die Maschine M ist erforderlich, um für die Polynomzeit für alle Eingaben zu lief, unabhängig vom Ergebnis der zufälligen Münzflips.

Alternative, BPP kann mit nur deterministischen Turing -Maschinen definiert werden. Eine Sprache L ist in BPP 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 ${\ displayStyle m (x, y) = 1}$ ist größer als oder gleich 2/3
• Für alle x nicht in L, der Bruchteil der Saiten y von Länge p(|x|) was befriedigt ${\ displayStyle m (x, y) = 1}$ ist kleiner als oder gleich 1/3

In dieser Definition die Zeichenfolge y Entspricht der Ausgabe der zufälligen Münzflips, die die probabilistische Turing -Maschine gemacht hätte. Für einige Anwendungen ist diese Definition vorzuziehen, da sie probabilistische Turing -Maschinen nicht erwähnt.

In der Praxis ist eine Fehlerwahrscheinlichkeit von 1/3 möglicherweise nicht akzeptabel, die Wahl von 1/3 in der Definition ist jedoch willkürlich. Ändern der Definition, um alle zu verwenden Konstante zwischen 0 und 1/2 (exklusiv) anstelle von 1/3 würde das resultierende Satz nicht ändern BPP. Wenn man beispielsweise die Klasse mit der Einschränkung definiert, dass der Algorithmus mit der Wahrscheinlichkeit höchst 1/2 falsch sein kann¹⁰⁰Dies würde zu der gleichen Probleme der Probleme führen. Die Fehlerwahrscheinlichkeit muss nicht einmal konstant sein: Die gleiche Problemklasse wird definiert, indem Fehler von bis zu 1/2 - zulässig ist n^−c Einerseits oder ein Fehler von nur klein wie 2 benötigt^−nc Andererseits wo c ist eine positive Konstante und n ist die Länge des Eingangs. Diese Flexibilität bei der Auswahl der Fehlerwahrscheinlichkeit basiert auf der Idee, einen fehleranfälligen Algorithmus mehrmals auszuführen und das Mehrheitsergebnis der Läufe zu verwenden, um einen genaueren Algorithmus zu erhalten. Die Chance, dass die Mehrheit der Läufe falsch ist fällt exponentiell ab als Folge der Tschernoff gebunden.^[1]

Probleme

Alle Probleme in P sind offensichtlich auch in BPP. Es ist jedoch bekannt BPP aber nicht bekannt dafür P. Die Anzahl solcher Probleme nimmt ab und wird vermutet, dass dies vermutet wird P = BPP.

Seit langer Zeit eines der bekanntesten Probleme, in denen bekannt ist, in denen bekannt ist BPP aber nicht bekannt dafür P war das Problem von bestimmen Ob eine bestimmte Zahl ist Prime. In der Arbeit von 2002 Primzahlen sind in P, Manindra Agrawal und seine Schüler Neeraj Kayal und Nitin Saxena fand einen deterministischen Polynom-Zeit-Algorithmus für dieses Problem und zeigt daher, dass es in ist P.

Ein wichtiges Beispiel für ein Problem in BPP (in der Tat in Co-RP) immer noch nicht bekannt dafür P ist Polynomidentitätstests, Das Problem, zu bestimmen, ob ein Polynom identisch gleich dem Nullpolynom ist, wenn Sie für einen bestimmten Eingang, jedoch nicht auf die Koeffizienten, auf den Wert des Polynoms zugreifen. Mit anderen Worten, gibt es eine Zuordnung von Werten zu den Variablen, so dass das Ergebnis ungleich Null ist, wenn ein Polynom ungleich Null auf diesen Werten bewertet wird? Es reicht aus, den Wert jeder Variablen durch eine endliche Teilmenge von mindestens zufällig auszuwählen d Werte, um eine begrenzte Fehlerwahrscheinlichkeit zu erreichen, wo d ist der Gesamtgrad des Polynoms.^[2]

Verwandte Klassen

Wenn der Zugriff auf Zufälligkeit aus der Definition von entfernt wird BPPWir bekommen die Komplexitätsklasse P. In der Definition der Klasse ersetzen wir das Gewöhnliche Turing Maschine mit einer Quantencomputerwir bekommen die Klasse BQP.

Hinzufügen Nachwahl zu BPPoder ermöglichen, dass Berechnungswege unterschiedliche Längen haben, gibt der Klasse BPP_Weg.^[3] BPP_Weg Es ist bekannt, dass es enthält Npund es ist in seinem Quanten -Gegenstück enthalten Postbqp.

A Monte Carlo Algorithmus ist ein Randomisierter Algorithmus das ist wahrscheinlich richtig. Probleme in der Klasse BPP haben Monte -Carlo -Algorithmen mit polynomisch begrenzter Laufzeit. Dies wird mit a verglichen Las Vegas Algorithmus Dies ist ein randomisierter Algorithmus, der entweder die richtige Antwort ausgibt oder mit niedriger Wahrscheinlichkeit "fehlschlägt". Las Vegas -Algorithmen mit polynomischen Laufzeiten werden verwendet, um die Klasse zu definieren Zpp. Alternative, Zpp Enthält probabilistische Algorithmen, die immer korrekt sind und die Polynomlaufzeit erwartet haben. Dies ist schwächer als zu sagen, dass es sich um einen Polynomzeitalgorithmus handelt, da es für die superpolynomiale Zeit, jedoch mit sehr geringer Wahrscheinlichkeit, ausgeführt werden kann.

Komplexitätstheoretische Eigenschaften

BPP in Bezug auf andere probabilistische Komplexitätsklassen (Zpp, RP, Co-RP, BQP, Pp), die verallgemeinern P innerhalb PSPACE. Es ist unbekannt, ob eine dieser Eindämme streng ist.

Es ist bekannt, dass BPP ist unter geschlossen ergänzen; das ist, BPP = CO-BPP. BPP ist niedrig für sich selbst, was bedeutet, dass a BPP Maschine mit der Leistung zu lösen BPP Probleme sofort (a BPP Oracle Machine) ist ohne diese zusätzliche Leistung nicht leistungsfähiger als die Maschine. In Symbolen, BPP^BPP = BPP.

Die Beziehung zwischen BPP und Np ist unbekannt: Es ist nicht bekannt, ob BPP ist ein Teilmenge von Np, Np ist eine Teilmenge von BPP oder auch nicht. Wenn Np ist in BPP, was als unwahrscheinlich angesehen wird, da es praktische Lösungen für bedeuten würde NP-Complete Probleme dann Np = RP und PH ⊆ BPP.^[4]

Es ist bekannt, dass RP ist eine Teilmenge von BPP, und BPP ist eine Teilmenge von Pp. Es ist nicht bekannt, ob diese beiden strenge Untergruppen sind, da wir nicht einmal wissen, ob P ist eine strenge Teilmenge von PSPACE. BPP ist in der zweiten Ebene der Polynomhierarchie und deshalb ist es in enthalten in PH. Genauer gesagt die SIPser -Lautemann -Theorem besagt, dass ${\ displaystyle {\ mathsf {bpp}} \ subseteq \ sigma _ {2} \ cap \ pi _ {2}}$. Als Ergebnis, P = Np führt zu P = BPP seit PH zusammenbricht zu P in diesem Fall. So entweder P = BPP oder P ≠ Np oder beides.

Adleman's Theorem gibt diese Mitgliedschaft in einer Sprache in an BPP kann durch eine Familie der Polynomgröße bestimmt werden Boolesche Schaltungen, was bedeutet BPP ist in P/poly.^[5] In der Tat als Folge des Beweises dieser Tatsache, jeder BPP Algorithmus, der auf Eingängen der begrenzten Länge arbeitet, kann unter Verwendung einer festen Zeichenfolge von Zufallsbits in einen deterministischen Algorithmus desandomisiert werden. Das Finden dieser Saite kann jedoch teuer sein. Einige schwache Trennungsergebnisse für Monte -Carlo -Zeitklassen wurden durch bewiesen Karpinski & Verbeek (1987a), siehe auch Karpinski & Verbeek (1987b).

Verschlusseigenschaften

Das BPP der Klasse ist unter Komplementation, Union und Kreuzung geschlossen.

Relativierung

Im Vergleich zu Orakel wissen wir, dass es Orakel a und b gibt, so dass P^A = BPP^A und P^B ≠ BPP^B. Darüber hinaus relativ zu a zufälliges Orakel mit Wahrscheinlichkeit 1, P = BPP und BPP ist streng enthalten in Np und Co-NP.^[6]

Es gibt sogar ein Orakel, in dem BPP = exp^Np (und damit p <np <bpp = exp = nexp),^[7] das kann iterativ wie folgt konstruiert werden. Für ein festes E^Np (Relativiert) Vollständiges Problem gibt das Orakel korrekte Antworten mit hoher Wahrscheinlichkeit, wenn sie von der Probleminstanz abgefragt wird, gefolgt von einer zufälligen Längezeichenfolge Kn (n ist eine Instanzlänge; k ist eine angemessene kleine Konstante). Beginnen mit n= 1. Für jede Instanz des Längenproblems n Beheben Sie Oracle Answers (siehe Lemma unten), um die Instanzausgabe zu beheben. Geben Sie als nächstes die Instanzausgaben für Abfragen an, die aus der Instanz bestehen Kn-Length String und behandeln Sie die Ausgabe für Längenabfragen ≤ ((k+1)n als fest und mit Längeninstanzen fortfahren n+1.

Lemma: Bei einem relativierten E^Npfür jedes teilweise konstruierte Orakel und Eingang der Länge nDer Ausgang kann durch Angabe von 2 fixiert werden^O(n) Oracle antwortet.
Nachweisen: Die Maschine wird simuliert und die Oracle-Antworten (die noch nicht festgelegt sind) sind Schritt für Schritt festgelegt. Es gibt höchstens eine Oracle -Abfrage pro deterministischem Berechnungsschritt. Für das relativisierte NP -Oracle beheben Sie nach Möglichkeit den Ausgang so, als ob Sie einen Berechnungspfad auswählen und die Antworten des Basis -Orakels beheben. Andernfalls ist keine Fixierung erforderlich, und so oder so gibt es höchstens 1 Antwort auf das Basis -Orakel pro Schritt. Da gibt es 2^O(n) Schritte folgt das Lemma.

Das Lemma stellt das sicher (für eine große genug große genug k) Es ist möglich, die Konstruktion durchzuführen und gleichzeitig genügend Saiten für das relativierte e zu verlassen^Np Antworten. Außerdem können wir sicherstellen, dass für das relativierte e^Np, lineare Zeit reicht auch für Funktionsprobleme (falls eine Funktion Oracle und lineare Ausgangsgröße) und mit exponentiell kleiner (mit linearer Exponent) Fehlerwahrscheinlichkeit. Außerdem ist diese Konstruktion insofern wirksam, wenn ein willkürliches Oracle A wir arrangieren können, um P zu haben^A≤p^B und exp^NpA= Exp^NpB= BPP^B. Auch für a Zpp= Exp Oracle (und damit zpp = bpp = exp <nexp) würde man die Antworten in der relativisierten E -Berechnung zu einem speziellen Nicht -Anbieter beheben und so sicherstellen, dass keine gefälschten Antworten angegeben werden.

Derandomisierung

Die Existenz bestimmter starker Pseudorandom -Zahlengeneratoren ist vermutet von den meisten Experten des Feldes. Diese Vermutung impliziert, dass Zufälligkeit keine zusätzliche Rechenleistung für die Polynomzeitberechnung ergibt, dh, P = RP = BPP. Beachten Sie, dass gewöhnliche Generatoren nicht ausreichen, um dieses Ergebnis zu zeigen. Jeder probabilistische Algorithmus, der unter Verwendung eines typischen Zufallszahlengenerators implementiert ist, führt immer zu falschen Ergebnissen bei bestimmten Eingaben, unabhängig vom Saatgut (obwohl diese Eingaben möglicherweise selten sein können).

László Babai, Lance Fortnow, Noam Nisan, und Avi Wigderson zeigte das, es sei denn Nachfolger zusammenbricht zu Ma, BPP ist in^[8]

${\ displayStyle {\ textsf {i.o.-subexp}} = \ bigcap \ nolimits _ {\ varepsilon> 0} {\ texsf {i.o.-dime}} \ links (2^{n^{\ varepSsilon}} \ rechts). }$

Die Klasse I.O.-SUBExp, was für unendlich oft steht Subexp, enthält Probleme, die haben Subexponentialzeit Algorithmen für unendlich viele Eingangsgrößen. Sie zeigten auch das P = BPP Wenn die Exponential-Zeit-Hierarchie, die in Bezug auf die definiert ist Polynomhierarchie und E wie E^PH, bricht zu E; Beachten Sie jedoch, dass die exponentielle Hierarchie normalerweise vermutet wird nicht zusammenbrechen.

Russell Impagliazzo und Avi Wigderson zeigte das, wenn ein Problem in E, wo

${\ displaystyle {\ mathsf {e}} = {\ mathsf {dtime}} \ links (2^{o (n)} \ rechts),},}$

hat Schaltungskomplexität 2^{Ω (n)} dann P = BPP.^[9]

Siehe auch

• RP
• Zpp
• BQP
• Liste der Komplexitätsklassen

Verweise

• Valentine Kabanets (2003). "CMPT 710 - Komplexitätstheorie: Vortrag 16". Simon Fraser Universität.
• Christos Papadimitriou (1993). Rechenkomplexität (1. Aufl.). Addison Wesley. ISBN 0-201-53082-1. Seiten 257–259 von Abschnitt 11.3: Zufällige Quellen. Seiten 269–271 von Abschnitt 11.4: Schaltkomplexität.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-x. Abschnitt 10.2.1: Die Klasse BPP, S. 336–339.
• Karpinski, Marek; Verbeek, Rutger (1987a). "Zufälligkeit, Proviertigkeit und die Trennung von Monte -Carlo -Zeit und -Raum". In Börger, Egon (Hrsg.). Berechnungstheorie und Logik im Gedächtnis von Dieter Rödding. Vorlesungsnotizen in Informatik. Vol. 270. Springer. S. 189–207. doi:10.1007/3-540-18170-9_166.
• Karpinski, Marek; Verbeek, Rutger (1987b). "Auf den Monte -Carlo -Platzkonstruktionsfunktionen und Trennungsergebnissen für probabilistische Komplexitätsklassen". Informationen und Berechnung. 75 (2): 178–189. doi:10.1016/0890-5401 (87) 90057-5.
• Arora, Sanjeev; Boaz Barak (2009). "Rechenkomplexität: ein moderner Ansatz".

Externe Links

• Princeton CS 597E: Derandomization Papierliste
• Harvard CS 225: Pseudorandomness Archiviert 2003-08-05 am Wayback -Maschine