die Komplexitätsklasse aller Entscheidungsprobleme, für die es einen randomisierten Algorithmus gibt, der das Problem so in polynomieller Zeit löst, daß für Eingaben, die nicht zu der zu erkennenden Sprache gehören, dies mit Sicherheit erkannt wird, und für Eingaben, die zu der zu erkennenden Sprache gehören, dies mit einer Wahrscheinlichkeit von mindestens 1/2 erkannt wird.

Da die Antwort, daß eine Eingabe akzeptiert wird, irrtumsfrei ist, haben RP-Algorithmen nur einseitigen Irrtum. Durch polynomiell viele unabhängige Wiederholungen des Algorithmus und der endgültigen Akzeptanz einer Eingabe, wenn sie in mindestens einem Durchlauf akzeptiert wird, kann die Irrtumswahrscheinlichkeit exponentiell klein gemacht werden. Damit sind RP-Algorithmen von großer praktischer Bedeutung. Die Abkürzung RP steht für random polynomial (time).

Die Klasse RP ist in der Klasse NP enthalten.