www.wikidata.de-de.nina.az

BPP Komplexitätsklasse In der Komplexitätstheorie steht BPP englische Abkürzung für bounded error probabilistic polynomi

BPP (Komplexitätsklasse)

In der Komplexitätstheorie steht BPP (englische Abkürzung für bounded error probabilistic polynomial time) für eine Komplexitätsklasse von Entscheidungsproblemen. Ein Problem liegt in BPP, wenn es einen polynomiell zeitbeschränkten probabilistischen Algorithmus gibt, der das Problem löst und dessen Fehlerwahrscheinlichkeit höchstens 1/3 beträgt. Die Verwendung einer beliebigen anderen konstanten Fehlerschranke kleiner als 1/2 ändert nichts an der Definition der Klasse BPP, durch mehrmalige Anwendung eines gegebenen BPP-Algorithmus lässt sich jede beliebige Fehlerschranke erreichen.

BPP-Algorithmen sind Monte-Carlo-Algorithmen, da sie mit einer geringen Wahrscheinlichkeit ein falsches Ergebnis liefern.

Sie wurde 1977 mit anderen probabilistischen Komplexitätsklassen von John T. Gill eingeführt.

Definition Bearbeiten

Eine Sprache liegt genau dann in der Komplexitätsklasse , wenn eine probabilistische Turing-Maschine existiert, für die gilt:

  • läuft für alle Eingaben in polynomieller Zeit

Die Konstante 2/3 ist willkürlich gewählt. Jede Konstante echt größer als 1/2 und sogar für eine Konstante (wobei die Eingabelänge ist) führt zu einer äquivalenten Definition.

Im Gegensatz zur Komplexitätsklasse ZPP wird hier gefordert, dass die Laufzeit der Turingmaschine für alle Eingaben polynomiell ist. Diese Forderung kann abgeschwächt werden, so dass wie bei ZPP nur noch gefordert wird, dass der Erwartungswert der Laufzeit durch ein Polynom beschränkt ist; die beiden Definitionen sind äquivalent.

Eigenschaften Bearbeiten

BPP ist abgeschlossen unter Komplementbildung, Vereinigung und Schnitt. Das bedeutet, dass für zwei Sprachen auch . Es ist also co-BPP = BPP.

Es ist kein BPP-vollständiges Problem bekannt und es gibt Hinweise darauf, dass es keine BPP-vollständigen Probleme gibt.

Beziehung zu anderen Komplexitätsklassen Bearbeiten

Inklusionen zwischen probabilistischen Komplexitätsklassen

Die Klasse BPP liegt zwischen den Klassen RP und co-RP, bei denen nur einseitige Fehler erlaubt sind, und PP, bei der lediglich eine Fehlerschranke kleiner 1/2 gefordert wird, die auch von der Eingabelänge abhängen darf. Es gilt also (RP co-RP) ⊆ BPP ⊆ PP. Es ist unbekannt, ob die Inklusionen echt sind, da P ⊆ RP und PP ⊆ PSPACE gilt.

Die Beziehung zur Klasse NP ist unbekannt, weder BPP ⊆ NP noch NP ⊆ BPP konnte bisher gezeigt werden, letzteres gilt aber als unwahrscheinlich. BPP liegt in der Polynomialzeithierarchie PH: Falls P = NP, kollabiert PH vollständig zu PH = P, in diesem Fall wäre BPP = P.

Die Klasse BQP ist das entsprechende Konzept zur Klasse BPP für Quantencomputer. Es gilt BPP ⊆ BQP.

Ein bedeutender Durchbruch in der Einschätzung von Zufallsalgorithmen gelang Avi Wigderson mit Russell Impagliazzo in den 1990er Jahren. Sie zeigten, das unter bestimmten Bedingungen schnelle Zufallsalgorithmen immer in deterministische Algorithmen umgewandelt werden können (mit geeigneten Pseudozufallsgeneratoren): die Komplexitätsklasse BPP ist unter einer häufig als zutreffend angenommenen Voraussetzung gleich der Komplexitätsklasse P. Die Voraussetzung ist, dass die Komplexitätsklasse E exponentielle Schaltkreiskomplexität hat.

Einzelnachweise Bearbeiten

  1. Christos H. Papadimitriou: Computational Complexity. Addison-Wesley, 1998, ISBN 0-201-53082-1, S. 259.
  2. Sanjeev Arora und Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, 2009, ISBN 978-0-521-42426-4, S. 125.
  3. Sanjeev Arora und Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, 2009, ISBN 978-0-521-42426-4, S. 132.
  4. Sanjeev Arora und Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, 2009, ISBN 978-0-521-42426-4, S. 133.
  5. ↑ Daniel Pierre Bovet und Pierluigi Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994, ISBN 0-13-915380-2, S. 195.
  6. Daniel Pierre Bovet und Pierluigi Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994, ISBN 0-13-915380-2, S. 198,202.
  7. Clemens Lautemann: BPP and the polynomial hierarchy. In: Information Processing Letters. Band 17, Nr. 4. Elsevier, 1983, S. 215–217, doi:10.1016/0020-0190(83)90044-3.
  8. Johannes Köbler, Uwe Schöning, Jacobo Torán: The Graph Isomorphism Problem - It's Structural Complexity. Birkhäuser, 1993, ISBN 3-7643-3680-3, S. 78.
  9. Kevin Hartnett, Pioneers Linking Math and Computer Science Win the Abel Prize, Quanta Magazine, 17. März 2021, anlässlich des Abelpreises 2021 zu einer Hälfte für Wigderson.
  10. R. Impagliazzo, A. Wigderson: P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In: 29th STOC, 1997, S. 220–229

Literatur Bearbeiten

  • J. Gill. Computational complexity of probabilistic Turing machines, SIAM Journal on Computing 6(4):675-695, 1977.
  • Christos H. Papadimitriou: Computational Complexity. Addison-Wesley, Reading/Mass. 1995, ISBN 0-201-53082-1.

Weblinks Bearbeiten

  • BPP. In: Complexity Zoo. (englisch)
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Komplexitatstheorie steht BPP englische Abkurzung fur bounded error probabilistic polynomial time fur eine Komplexitatsklasse von Entscheidungsproblemen Ein Problem liegt in BPP wenn es einen polynomiell zeitbeschrankten probabilistischen Algorithmus gibt der das Problem lost und dessen Fehlerwahrscheinlichkeit hochstens 1 3 betragt Die Verwendung einer beliebigen anderen konstanten Fehlerschranke kleiner als 1 2 andert nichts an der Definition der Klasse BPP durch mehrmalige Anwendung eines gegebenen BPP Algorithmus lasst sich jede beliebige Fehlerschranke erreichen 1 BPP Algorithmen sind Monte Carlo Algorithmen da sie mit einer geringen Wahrscheinlichkeit ein falsches Ergebnis liefern Sie wurde 1977 mit anderen probabilistischen Komplexitatsklassen von John T Gill eingefuhrt Inhaltsverzeichnis 1 Definition 2 Eigenschaften 3 Beziehung zu anderen Komplexitatsklassen 4 Einzelnachweise 5 Literatur 6 WeblinksDefinition BearbeitenEine Sprache L displaystyle mathcal L nbsp liegt genau dann in der Komplexitatsklasse B P P displaystyle mathcal BPP nbsp wenn eine probabilistische Turing Maschine M displaystyle M nbsp existiert fur die gilt 2 M displaystyle M nbsp lauft fur alle Eingaben in polynomieller Zeit x L P r M x 1 2 3 displaystyle x in mathcal L Rightarrow Pr M x 1 geq frac 2 3 nbsp x L P r M x 0 2 3 displaystyle x notin mathcal L Rightarrow Pr M x 0 geq frac 2 3 nbsp Die Konstante 2 3 ist willkurlich gewahlt Jede Konstante echt grosser als 1 2 und sogar 1 2 x c displaystyle frac 1 2 x c nbsp fur eine Konstante c gt 0 displaystyle c gt 0 nbsp wobei x displaystyle x nbsp die Eingabelange ist fuhrt zu einer aquivalenten Definition 3 Im Gegensatz zur Komplexitatsklasse ZPP wird hier gefordert dass die Laufzeit der Turingmaschine M displaystyle M nbsp fur alle Eingaben polynomiell ist Diese Forderung kann abgeschwacht werden so dass wie bei ZPP nur noch gefordert wird dass der Erwartungswert der Laufzeit durch ein Polynom beschrankt ist die beiden Definitionen sind aquivalent 4 Eigenschaften BearbeitenBPP ist abgeschlossen unter Komplementbildung Vereinigung und Schnitt 5 Das bedeutet dass fur zwei Sprachen L 1 L 2 B P P displaystyle L 1 L 2 in mathcal BPP nbsp auch L 1 c L 1 L 2 L 1 L 2 B P P displaystyle L 1 c L 1 cup L 2 L 1 cap L 2 in mathcal BPP nbsp Es ist also co BPP BPP Es ist kein BPP vollstandiges Problem bekannt und es gibt Hinweise darauf dass es keine BPP vollstandigen Probleme gibt 6 Beziehung zu anderen Komplexitatsklassen Bearbeiten nbsp Inklusionen zwischen probabilistischen KomplexitatsklassenDie Klasse BPP liegt zwischen den Klassen RP und co RP bei denen nur einseitige Fehler erlaubt sind und PP bei der lediglich eine Fehlerschranke kleiner 1 2 gefordert wird die auch von der Eingabelange abhangen darf Es gilt also RP displaystyle cup nbsp co RP BPP PP 5 Es ist unbekannt ob die Inklusionen echt sind da P RP und PP PSPACE gilt Die Beziehung zur Klasse NP ist unbekannt weder BPP NP noch NP BPP konnte bisher gezeigt werden letzteres gilt aber als unwahrscheinlich BPP liegt in der Polynomialzeithierarchie PH B P P S 2 P P 2 P displaystyle mathcal BPP subseteq Sigma 2 P cap Pi 2 P nbsp 7 8 Falls P NP kollabiert PH vollstandig zu PH P in diesem Fall ware BPP P Die Klasse BQP ist das entsprechende Konzept zur Klasse BPP fur Quantencomputer Es gilt BPP BQP Ein bedeutender Durchbruch in der Einschatzung von Zufallsalgorithmen gelang Avi Wigderson mit Russell Impagliazzo in den 1990er Jahren 9 Sie zeigten das unter bestimmten Bedingungen schnelle Zufallsalgorithmen immer in deterministische Algorithmen umgewandelt werden konnen mit geeigneten Pseudozufallsgeneratoren die Komplexitatsklasse BPP ist unter einer haufig als zutreffend angenommenen Voraussetzung gleich der Komplexitatsklasse P 10 Die Voraussetzung ist dass die Komplexitatsklasse E exponentielle Schaltkreiskomplexitat hat Einzelnachweise Bearbeiten Christos H Papadimitriou Computational Complexity Addison Wesley 1998 ISBN 0 201 53082 1 S 259 Sanjeev Arora und Boaz Barak Computational Complexity A Modern Approach Cambridge University Press 2009 ISBN 978 0 521 42426 4 S 125 Sanjeev Arora und Boaz Barak Computational Complexity A Modern Approach Cambridge University Press 2009 ISBN 978 0 521 42426 4 S 132 Sanjeev Arora und Boaz Barak Computational Complexity A Modern Approach Cambridge University Press 2009 ISBN 978 0 521 42426 4 S 133 a b Daniel Pierre Bovet und Pierluigi Crescenzi Introduction to the Theory of Complexity Prentice Hall 1994 ISBN 0 13 915380 2 S 195 Daniel Pierre Bovet und Pierluigi Crescenzi Introduction to the Theory of Complexity Prentice Hall 1994 ISBN 0 13 915380 2 S 198 202 Clemens Lautemann BPP and the polynomial hierarchy In Information Processing Letters Band 17 Nr 4 Elsevier 1983 S 215 217 doi 10 1016 0020 0190 83 90044 3 Johannes Kobler Uwe Schoning Jacobo Toran The Graph Isomorphism Problem It s Structural Complexity Birkhauser 1993 ISBN 3 7643 3680 3 S 78 Kevin Hartnett Pioneers Linking Math and Computer Science Win the Abel Prize Quanta Magazine 17 Marz 2021 anlasslich des Abelpreises 2021 zu einer Halfte fur Wigderson R Impagliazzo A Wigderson P BPP if E requires exponential circuits Derandomizing the XOR Lemma In 29th STOC 1997 S 220 229Literatur BearbeitenJ Gill Computational complexity of probabilistic Turing machines SIAM Journal on Computing 6 4 675 695 1977 Christos H Papadimitriou Computational Complexity Addison Wesley Reading Mass 1995 ISBN 0 201 53082 1 Weblinks BearbeitenBPP In Complexity Zoo englisch Abgerufen von https de wikipedia org w index php title BPP Komplexitatsklasse amp oldid 222959836