In der rechenbetonten Kompliziertheitstheorie ist begrenzter Fehler probabilistic polynomische Zeit (BPP) die Klasse von Entscheidungsproblemen, die durch eine probabilistic Maschine von Turing in der polynomischen Zeit, mit einer Fehlerwahrscheinlichkeit am grössten Teil von 1/3 für alle Beispiele lösbar sind.

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

• Es wird erlaubt, Münzen zu schnipsen und zufällige Entscheidungen zu treffen

Wie man

• versichert, läuft es in der polynomischen Zeit
• Auf jedem gegebenen Lauf des Algorithmus hat es eine Wahrscheinlichkeit am grössten Teil von 1/3, die falsche Antwort zu geben, ob die Antwort JA oder NEIN ist.

Einführung

BPP ist eine der größten praktischen Klassen von Problemen, bedeutend, dass die meisten Probleme von Interesse in BPP effiziente probabilistic Algorithmen haben, die schnell auf echten modernen Maschinen geführt werden können. Aus diesem Grund ist es von großem praktischem Interesse, das Probleme und Klassen von Problemen innerhalb von BPP sind. BPP enthält auch P, die Klasse von Problemen, die in der polynomischen Zeit mit einer deterministischen Maschine lösbar sind, da eine deterministische Maschine ein spezieller Fall einer probabilistic Maschine ist.

In der Praxis könnte eine Fehlerwahrscheinlichkeit von 1/3 nicht jedoch annehmbar sein, die Wahl von 1/3 in der Definition ist willkürlich. Es kann jede Konstante zwischen 0 und 1/2 (exklusiv) und der Satz sein BPP wird unverändert sein. Es muss nicht sogar unveränderlich sein: Dieselbe Klasse von Problemen wird durch das Erlauben des Fehlers nicht weniger als 1/2  n einerseits oder das Verlangen des Fehlers mindestens 2 andererseits definiert, wo c jede positive Konstante ist, und n die Länge des Eingangs ist. Die Idee besteht darin, dass es eine Wahrscheinlichkeit des Fehlers gibt, aber wenn der Algorithmus oft geführt wird, hat die Chance, dass die Mehrheit der Läufe falsche Fälle von exponential demzufolge des Chernoffs ist, gebunden. Das macht es möglich, einen hoch genauen Algorithmus durch das bloße Laufen des Algorithmus mehrere Male und die Einnahme einer "Majoritätsstimme" der Antworten zu schaffen. Zum Beispiel, wenn man die Klasse mit der Beschränkung definieren würde, dass der Algorithmus mit der Wahrscheinlichkeit am grössten Teil von 1/2 falsch sein kann, würde das auf dieselbe Klasse von Problemen hinauslaufen.

Definition

Eine Sprache L ist in BPP, wenn, und nur wenn dort eine probabilistic Maschine von Turing M, solch dass besteht

• M Läufe für die polynomische Zeit auf allen Eingängen
• Für den ganzen x in L, M Produktionen 1 mit der Wahrscheinlichkeit größer oder gleich 2/3
• Für den ganzen x nicht in L, M Produktionen 1 mit der Wahrscheinlichkeit weniger als oder gleich 1/3

Verschieden von der Kompliziertheitsklasse ZPP die Maschine ist M erforderlich, für die polynomische Zeit auf allen Eingängen unabhängig vom Ergebnis der zufälligen Münzflips zu laufen.

Wechselweise kann BPP mit nur deterministische Maschinen von Turing definiert werden. Eine Sprache L ist in BPP, wenn, und nur wenn dort ein Polynom p und deterministische Maschine von Turing M, solch dass besteht

M Läufe für die polynomische Zeit auf allen Eingängen

• Für den ganzen x in L ist der Bruchteil von Schnuren y der Länge p (x), die M (x, y) = 1 befriedigen, größer oder gleich 2/3
• Für den ganzen x in nicht in L ist der Bruchteil von Schnuren y der Länge p (x), die M (x, y) = 1 befriedigen, weniger als oder gleich 1/3

In dieser Definition entspricht die Schnur y der Produktion der zufälligen Münzflips, die die probabilistic Maschine von Turing gemacht hätte. Für einige Anwendungen ist diese Definition vorzuziehend, da sie probabilistic Maschinen von Turing nicht erwähnt.

Probleme

Außer den Problemen in P, die offensichtlich in BPP sind, wie man bekannt war, waren viele Probleme in BPP, aber nicht bekannt, in P zu sein. Die Zahl solcher Probleme nimmt ab, und sie wird das P = BPP vermutet.

Seit langem war eines der berühmtesten Probleme, das, wie man bekannt war, in BPP war, aber nicht bekannt, in P zu sein, das Problem der Bestimmung, ob eine gegebene Zahl erst ist. Jedoch, in der 2002-Papier-BLÜTE ist in P, Manindra Agrawal und seinen Studenten Neeraj Kayal, und Nitin Saxena hat einen deterministischen polynomisch-maligen Algorithmus für dieses Problem gefunden, so zeigend, dass es in P ist.

Ein wichtiges Beispiel eines Problems in BPP (tatsächlich in der Handelsgesellschaft) noch immer nicht bekannt, in P zu sein, ist polynomische Identitätsprüfung, das Problem der Bestimmung, ob ein Polynom dem Nullpolynom identisch gleich ist. Mit anderen Worten gibt es eine Anweisung von solchen Variablen, dass, wenn das Polynom bewertet wird, das Ergebnis Nichtnull ist? Es genügt, um den Wert jeder Variable gleichförmig aufs Geratewohl aus einer begrenzten Teilmenge mindestens d Werte zu wählen, um begrenzte Fehlerwahrscheinlichkeit zu erreichen, wo d der Gesamtgrad des Polynoms ist.

Zusammenhängende Klassen

Wenn der Zugang zur Zufälligkeit von der Definition von BPP entfernt wird, bekommen wir die Kompliziertheitsklasse P. In der Definition der Klasse, wenn wir die gewöhnliche Maschine von Turing durch einen Quant-Computer ersetzen, bekommen wir die Klasse BQP.

Das Hinzufügen der Postauswahl zu BPP oder das Erlauben von Berechnungspfade, verschiedene Längen zu haben, geben der Klasse BPP. Wie man bekannt, enthält BPP NP, und es wird in seinem Quant-Kollegen PostBQP enthalten.

Ein Algorithmus von Monte Carlo ist ein randomized Algorithmus, der wahrscheinlich richtig sein wird. Probleme in der Klasse BPP haben Algorithmen von Monte Carlo mit dem Polynom, haben Laufzeit begrenzt. Das ist im Vergleich zu einem Las Vegas Algorithmus, der ein randomized Algorithmus ist, dem entweder Produktionen die richtige Antwort oder Produktionen mit der niedrigen Wahrscheinlichkeit "fehlt". Las Vegas Algorithmen mit dem Polynom haben gebunden Laufzeiten werden verwendet, um die Klasse ZPP zu definieren. Wechselweise enthält ZPP probabilistic Algorithmen, die immer richtig sind und polynomische Laufzeit erwartet haben. Das ist schwächer als Ausspruch, dass es ein polynomischer Zeitalgorithmus ist, da es für die superpolynomische Zeit, aber mit der sehr niedrigen Wahrscheinlichkeit laufen kann.

Mit der Kompliziertheit theoretische Eigenschaften

Es ist bekannt, dass BPP unter der Ergänzung geschlossen wird; d. h. BPP = co-BPP. BPP ist für sich niedrig, bedeutend, dass eine BPP Maschine mit der Macht, BPP Probleme sofort (eine BPP Orakel-Maschine) zu beheben, nicht mehr stark ist als die Maschine ohne diese Extramacht. In Symbolen, BPP = BPP.

Die Beziehung zwischen BPP und NP ist unbekannt: Es ist nicht bekannt, ob BPP eine Teilmenge von NP ist, ist NP eine Teilmenge von BPP, oder wenn sie unvergleichbar sind. Wenn NP in BPP enthalten wird, der unwahrscheinlich betrachtet wird, da es praktische Lösungen für NP-complete Probleme, dann NP = RP und PH  BPP einbeziehen würde.

Es ist bekannt, dass RP eine Teilmenge von BPP ist, und BPP eine Teilmenge von SEITEN ist. Es ist nicht bekannt, ob jene zwei strenge Teilmengen sind, da wir nicht sogar wissen, ob P eine strenge Teilmenge von PSPACE ist. BPP wird im zweiten Niveau der polynomischen Hierarchie enthalten, und deshalb wird es im PH enthalten. Genauer stellt der Lehrsatz von Sipser-Lautemann dass BPP  Σ  Π fest. Infolgedessen P = führt NP zu P = BPP seit PH-Zusammenbrüchen zu P in diesem Fall. So entweder P = BPP oder P  NP oder beide.

Der Lehrsatz von Adleman stellt fest, dass die Mitgliedschaft auf jeder Sprache in BPP von einer Familie der polynomischen Größe Stromkreise von Boolean bestimmt werden kann, was bedeutet, dass BPP in P/poly enthalten wird. Tatsächlich, demzufolge des Beweises dieser Tatsache, kann jeder BPP Algorithmus, der auf Eingängen der begrenzten Länge funktioniert, derandomized in einen deterministischen Algorithmus mit einer festen Schnur von zufälligen Bit sein. Entdeckung dieser Schnur kann jedoch teuer sein.

Hinsichtlich Orakel wissen wir, dass dort Orakel A und B, solch dass P = BPP und P  BPP bestehen. Außerdem, hinsichtlich eines zufälligen Orakels mit der Wahrscheinlichkeit 1, P = werden BPP und BPP in NP und co-NP ausschließlich enthalten.

Derandomization

Die Existenz von bestimmten starken Pseudozufallszahlengeneratoren wird von den meisten Experten des Feldes vermutet. Diese Vermutung deutet an, dass Zufälligkeit zusätzliche rechenbetonte Macht zur polynomischen Zeitberechnung, d. h. P = RP = BPP nicht gibt. Bemerken Sie, dass gewöhnliche Generatoren nicht genügend sind, um dieses Ergebnis zu zeigen; das durchgeführte Verwenden jedes probabilistic Algorithmus eines typischen Zufallszahlengenerators wird immer falsche Ergebnisse auf bestimmten Eingängen ohne Rücksicht auf den Samen erzeugen (obwohl diese Eingänge selten sein könnten).

László Babai, Lance Fortnow, Noam Nisan und Avi Wigderson haben das gezeigt, wenn EXPTIME-Zusammenbrüche dem Magister artium, BPP in i.o.-SUBEXP = nicht enthalten wird. Die Klasse i.o.-SUBEXP, der ungeheuer häufig für SUBEXP eintritt, enthält Probleme, die Subexponentialzeitalgorithmen für ungeheuer viele Eingangsgrößen haben. Sie haben auch gezeigt, dass P = BPP wenn die exponentialmalige Hierarchie, die in Bezug auf die polynomische Hierarchie und E als E, Zusammenbrüche zu E definiert wird; bemerken Sie jedoch, dass die exponentialmalige Hierarchie gewöhnlich vermutet wird, um nicht zusammenzubrechen.

Russell Impagliazzo und Avi Wigderson haben das gezeigt, wenn ein Problem in E, wo, Stromkreis-Kompliziertheit dann P = BPP hat.

• Seiten 257-259 des Abschnitts 11.3: Zufällige Quellen. Seiten 269-271 des Abschnitts 11.4: Stromkreis-Kompliziertheit.

• Abschnitt 10.2.1: Die Klasse BPP, Seiten 336-339.

Außenverbindungen

• Princeton CS 597E: Papier von Derandomization verzeichnet
• Harvard CS 225: Pseudozufälligkeit