Das Kefk Network Wiki befindet sich im Testbetrieb.

BPP (Komplexitätsklasse)

Aus Kefk.

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 dabei eine Fehlerwahrscheinlichkeit von weniger als 1/3 hat. 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.

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)