die Komplexitätsklasse aller Probleme, für die es einen randomisierten Algorithmus gibt, der das Problem so in polynomieller Zeit löst, daß für ein ϵ > 0 die richtige Lösung mit einer Wahrscheinlichkeit von mindestens 1/2 + ϵ berechnet wird.

Durch polynomiell viele unabhängige Wiederholungen des Algorithmus und eine Entscheidung für die am häufigsten berechnete Lösung kann die Irrtumswahrscheinlichkeit exponentiell klein gemacht werden. Damit sind BPP-Algorithmen von großer praktischer Bedeutung.

Die Abkürzung BPP steht für bounded-error probabilistic polynomial (time). BPP-Algorithmen erlauben bei Entscheidungsproblemen einen zweiseitigen Irrtum, da statt der richtigen Antwort 0 die falsche Antwort 1 möglich ist und umgekehrt. Es wird vermutet, daß die Einschränkung von BPP auf Entscheidungsprobleme und NP unvergleichbar sind.