RP randomizowany czas wielomianowy jest klasą złożoności obliczeniowej teorii złożoności, problemów, dla których istnieje probabilistyczna maszyna Turinga o następujących właściwościach:⁕zawsze działa w czasie wielomianowym w rozmiarze wejściowym⁕jeśli poprawna odpowiedź brzmi nie, zawsze zwraca nie⁕jeśli poprawna odpowiedź brzmi tak, to zwraca tak z prawdopodobieństwem co najmniej 1/2.innymi słowy, algorytm może rzucić prawdziwie losową monetę podczas pracy. Jedynym przypadkiem, w którym algorytm może zwrócić YES, jest to, że rzeczywista odpowiedź brzmi YES; dlatego jeśli algorytm zakończy działanie i wykona tak, to poprawna odpowiedź jest zdecydowanie tak; jednak algorytm może zakończyć się bez względu na rzeczywistą odpowiedź. Oznacza to, że jeśli algorytm zwróci nie, może to być błędne.Niektórzy autorzy nazywają tę klasę R, chociaż nazwa ta jest częściej używana dla klasy języków rekurencyjnych.Jeśli prawidłowa odpowiedź brzmi tak, a algorytm jest uruchamiany n razy z wynikiem każdego biegu statystycznie niezależnym od pozostałych, to zwróci tak przynajmniej raz z prawdopodobieństwem co najmniej 1-2 -. Jeśli więc algorytm jest uruchamiany 100 razy, wówczas szansa na udzielenie błędnej odpowiedzi za każdym razem jest mniejsza niż szansa, że promieniowanie kosmiczne uszkodziło pamięć komputera uruchamiającego algorytm. W tym sensie, jeśli dostępne jest źródło liczb losowych, większość algorytmów w RP jest wysoce praktyczna.

Zobacz więcej ”