BPP (Komplexität)

In der theoretischen Informatik , insbesondere in der Komplexitätstheorie , ist die BPP-Klasse ( probabilistische Polynomzeit mit begrenztem Fehler) die Klasse von Entscheidungsproblemen, die von einer probabilistischen Turing-Maschine im Zeitpolynom mit einer Fehlerwahrscheinlichkeit in der Antwort von weniger als 1/3 entschieden werden .

Definition

Erste Definition

Die BPP-Klasse ist die Menge von Problemen oder in einer äquivalenten Art von Sprachen , für die es eine probabilistische Turing-Maschine in Polynomzeit gibt, die die folgenden Akzeptanzbedingungen erfüllt:

• Wenn das Wort nicht in der Sprache ist, lehnt die Maschine es mit einer Wahrscheinlichkeit von mehr als 2/3 ab.
• Wenn das Wort in der Sprache ist, akzeptiert die Maschine es mit einer Wahrscheinlichkeit von mehr als 2/3.

Mit anderen Worten, die Maschine ist mit einer Wahrscheinlichkeit von weniger als 1/3 falsch.

Formale Definition

Wir definieren die BPP- Klasse als die Menge von Sprachen, so dass es ein Polynom und eine Sprache gibt , die dies für jedes Wort bestätigt  : L.{\ displaystyle L}p((nicht){\ displaystyle p (n)}BEIM∈P.{\ displaystyle A \ in {\ rm {P}}}x{\ displaystyle x}

• x∈L.⇒P.rε∈{0,1}}p((|x|)((((x,ε)∈BEIM)≥23{\ displaystyle x \ in L \ Rightarrow {\ underset {\ varepsilon \ in \ {0,1 \} ^ {p (| x |)}} {Pr}} ((x, \ varepsilon) \ in A) \ geq {\ frac {2} {3}}}.
• x∉L.⇒P.rε∈{0,1}}p((|x|)((((x,ε)∈BEIM)≤13{\ displaystyle x \ notin L \ Rightarrow {\ underset {\ varepsilon \ in \ {0,1 \} ^ {p (| x |)}} {Pr}} ((x, \ varepsilon) \ in A) \ leq {\ frac {1} {3}}}.

Beziehungen zu anderen Klassen

Deterministische versus probabilistische Polynomzeit

Wir können eine probabilistische Maschine verwenden, um eine deterministische Berechnung durchzuführen , und daher P BPP . Die andere Einbeziehung ist eine offene Frage. Allgemeiner ausgedrückt lautet die Frage, ob die Zufälligkeit nützlich ist, um die Berechnung zu beschleunigen, oder nicht. Es gab eine Meinungsänderung seitens der Komplexitätsgemeinschaft zu diesem Thema: Bis in die 1980er Jahre dachten die meisten Forscher, BPP sei anders als P, und dann störten verschiedene Ergebnisse diese Überzeugung. Heute wird oft ein Unentschieden in Betracht gezogen. ⊆{\ displaystyle \ scriptstyle \ subseteq}

Andere Beziehungen

BPP enthält auch die Wahrscheinlichkeitsklassen, deren Akzeptanzbedingungen stärker sind als ZPP , RP und Co-RP .

Mit den Notationen der Polynomhierarchie haben wir nach dem Theorem von Sipser - Gács - Lautemann . B.P.P.⊆Σ2p∩Π2p{\ displaystyle BPP \ subseteq \ Sigma _ {2} ^ {p} \ cap \ Pi _ {2} ^ {p}}

In der Welt der Booleschen Schaltungsklassen gibt der Satz von Adleman BPP P / poly an ( Adleman 1978 ). ⊆{\ displaystyle \ scriptstyle \ subseteq}

Die Quantenvariante von BPP ist BQP .

Eigenschaften und Theoreme

• Bei Bedarf können wir effizientere Maschinen haben, dh wir können 2/3 durch und 1/3 durch (für sehr junge) ersetzen , ohne die Klasse zu ändern. Dieser Schub kann erreicht werden, indem die Maschine mehrmals unabhängig geworfen und abgestimmt wird. Die Berechnung verwendet die Chernoff-Grenzen .1- -ϵ{\ displaystyle 1- \ epsilon}ϵ{\ displaystyle \ epsilon}ϵ{\ displaystyle \ epsilon}

• BPP wird durch Komplementär geschlossen, dh BPP = Co-BPP.

Geschichte

Diese Klasse wurde von J. Gill in dem Artikel Computerkomplexität probabilistischer Turing-Maschinen zur gleichen Zeit wie die RP- und ZPP- Klassen eingeführt .

Literaturverzeichnis

• (en) Sanjeev Arora und Boaz Barak , Computerkomplexität: Ein moderner Ansatz , Cambridge University Press ,2009( ISBN  0-521-42426-7 ) , Kap.  7 ("Randomisierte Berechnung")
• Leonard. M. Adleman , "Zwei Sätze zur zufälligen Polynomzeit" , in Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science ,197875–83  p. ( DOI  10.1109 / SFCS.1978.37 )

Externer Link

• ( fr ) Die BPP-Klasse im Complexity Zoo

Anmerkungen und Referenzen

1. Sylvain Perifel , Algorithmische Komplexität , Ellipsen ,2014432  p. ( ISBN  9782729886929 , online lesen ) , Kap.  12.1 ("Derandomisierung")p. 318.
2. (in) Sanjeev Arora und Boaz Barak , Computerkomplexität: Ein moderner Ansatz , Cambridge University Press ,2009( ISBN  0-521-42426-7 ) , Kap.  7Abschnitt 5.2 BPP ist in PH
3. Komplexitätszoo
4. (in) John Gill , "  Computerkomplexität der probabilistischen Turingmaschine  " , SIAM Journal we Computing , vol.  6, n o  4, 1977, p.  675-695

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">