beschränkte Fehlerwahrscheinlichkeit probabilistische polynomielle Zeit

Einfache Sprache

Def. beschränkte Fehlerwahrscheinlichkeit probabilistische polynomielle Zeit

Beschränkte Fehlerwahrscheinlichkeit probabilistische polynomielle Zeit (BPP) ist die Klasse der Sprachen die durch eine Probabilistische Turingmaschine in Polynomialzeit mit einer Fehlerwahrscheinlichkeit $\frac{1}{3}$ entscheidet.

Bemerke: Die Festlegung auf eine Fehlerwahrscheinlichkeit $\frac{1}{3}$ ist arbiträr, da jede andere Fehlerwahrscheinlichkeit zwischen $0$ und $\frac{1}{2}$ nach dem Verstärkungslemma in Polynomialzeit Äquivalent sind.