RP randomizált polinom idő a komplexitás osztály számítási komplexitás elmélet, problémák, amelyekre a valószínűségi Turing-gép létezik ezekkel a tulajdonságokkal: ha a helyes válasz nem, akkor mindig fut polinom időben a bemeneti méret, ha a helyes válasz igen, akkor visszatér igen valószínűséggel legalább 1/2.más szóval, az algoritmus hagyjuk, hogy flip egy valóban véletlenszerű érme futás közben. Az egyetlen eset, amikor az algoritmus igen, ha a tényleges válasz igen; ezért, ha az algoritmus véget ér, és igen, akkor a helyes válasz határozottan igen; azonban az algoritmus a tényleges választól függetlenül véget érhet a nemmel. Vagyis, ha az algoritmus nem-et ad vissza, akkor lehet, hogy rossz.Egyes szerzők ezt az osztályt hívják R, bár ezt a nevet gyakrabban használják a rekurzív nyelvek osztályára.Ha a helyes válasz igen, és az algoritmus n-szer fut, az egyes futások eredménye statisztikailag független a többitől, akkor legalább egyszer igen, legalább 1 − 2−valószínűséggel tér vissza. Tehát, ha az algoritmust 100-szor futtatják, akkor annak az esélye, hogy minden alkalommal rossz választ ad, alacsonyabb, mint annak az esélye, hogy a kozmikus sugarak megrongálták az algoritmust futtató számítógép memóriáját. Ebben az értelemben, ha rendelkezésre áll véletlen számok forrása, az RP legtöbb algoritmusa nagyon praktikus.

többet látni ”