Randomisierte polynomielle Zeit

Einfache Sprache

Def. Randomisierte polynomielle Zeit

Randomisierte polynomielle Zeit (RP) ist die Klasse der Sprachen die durch eine Probabilistische Turingmaschine in Polynomialzeit mit einer Fehlerwahrscheinlichkeit $\frac{1}{2}$ für Wörter in der Sprache und mit Fehlerwahrscheinlichkeit $0$ für Wörter außerhalb der Sprache entscheidet.

Auch hier ist wie in BPP das Verstärkungslemma anwendbar.