BPP (Komplexitätsklasse)

In der Komplexitätstheorie steht BPP (engl. bounded error probability polynomial time) für eine Komplexitätsklasse von Entscheidungsproblemen. Ein Problem liegt in BPP, wenn es eine polynomiell zeitbeschränkte probabilistische Turingmaschine gibt, die das Problem löst und deren Fehlerwahrscheinlichkeit innerhalb [0, 1/2) liegt. Die Verwendung einer beliebigen anderen 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.

Beziehung zu anderen Komplexitätsklassen

Die Klasse BPP liegt zwischen den Klassen RP und PP, es gilt also RP ⊆ BPP ⊆ PP. Die Beziehung zur Klasse NP ist unbekannt, weder BPP ⊆ NP noch NP ⊆ BPP konnte bisher gezeigt werden.

BPP \subseteq \Sigma^{P}_{2} \cap \Pi^{P}_{2} (siehe Polynomialzeithierarchie)

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

Literatur

  • J. Gill. Computational complexity of probabilistic Turing machines, SIAM Journal on Computing 6(4):675-695, 1977

Weblinks

  • BPP. In: Complexity Zoo. (englisch)

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • BPP — Die Abkürzung BPP steht für: Bayerische Politische Polizei Beam Parameter Product, ein Begriff aus der Optik Bin Packing Problem, ein NP schweres kombinatorisches Optimierungsproblem Black Panther Party BPP (Komplexitätsklasse), ein Begriff aus… …   Deutsch Wikipedia

  • Co-RP (Komplexitätsklasse) — co RP (random polynominal) bzw. co RP(ε(n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomineller maximaler Rechenzeit gibt, der jede zu akzeptierende Eingabe mit Wahrscheinlichkeit 1… …   Deutsch Wikipedia

  • BQP (Komplexitätsklasse) — Die Komplexitätsklasse BQP (bounded error quantum polynomial time) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik. Zu BQP gehören alle Probleme, die auf einem Quantencomputer in Polynomialzeit mit einer …   Deutsch Wikipedia

  • RP (Komplexitätsklasse) — RP (random polynomial) bzw. RP( (n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus A mit polynomieller Laufzeit gibt, der jede nicht zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 ablehnt und für… …   Deutsch Wikipedia

  • Falltürfunktion — Eine Einwegfunktion im strengen Sinn ist eine mathematische Funktion, die komplexitätstheoretisch „schwer“ umzukehren ist. In einem erweiterten Sinn werden auch Funktionen so bezeichnet, zu denen bisher keine praktisch ausführbare Umkehrung… …   Deutsch Wikipedia

  • Co-RP — (random polynominal) bzw. co RP( (n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomineller maximaler Rechenzeit gibt, der jede zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 annimmt… …   Deutsch Wikipedia

  • BQP — Die Komplexitätsklasse BQP (bounded error quantum polynomial time) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik. Zu BQP gehören alle Probleme, die auf einem Quantencomputer in Polynomialzeit mit einer …   Deutsch Wikipedia

  • Monte-Carlo-Integration — Monte Carlo Algorithmen sind randomisierte Algorithmen, die mit einer nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern dürfen. Dafür sind sie im Vergleich zu deterministischen Algorithmen häufig effizienter. Ihr Nachteil… …   Deutsch Wikipedia

  • Komplexitätstheorie — Die Komplexitätstheorie als Teilgebiet der Theoretischen Informatik befasst sich mit der Komplexität von algorithmisch behandelbaren Problemen auf verschiedenen mathematisch definierten formalen Rechnermodellen. Die Komplexität von Algorithmen… …   Deutsch Wikipedia

  • Einwegfunktion — In der Informatik ist eine Einwegfunktion eine mathematische Funktion, die komplexitätstheoretisch „leicht“ berechenbar, aber „schwer“ umzukehren ist. In einem erweiterten Sinn werden auch Funktionen so bezeichnet, zu denen bisher keine in… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”