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)