27. Jul 2008, 11:38

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 zwischen 0 und 1/2 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. BPP-Algorithmen sind Monte-Carlo-Algorithmen, da sie mit einer geringen Wahrscheinlichkeit ein falsches Ergebnis liefern.

[Bearbeiten] 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.

(siehe Polynomialzeithierarchie)

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

[Bearbeiten] Literatur

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

[Bearbeiten] Weblinks

• BPP im Complexity Zoo (englisch)

Dieser Artikel ist eine Kopie aus der freien Enzyklopädie Wikipedia. Am Originalartikel kann jeder Korrekturen und Ergänzungen vornehmen. Zudem kann man frühere Versionen einsehen.

Abkürzungen • Dateiendungen • Netzjargon