Direkt zum Inhalt

Lexikon der Mathematik: BPP

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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos