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.