Rp timpul polinomial randomizat este clasa de complexitate a teoriei complexității computaționale, probleme pentru care există o mașină Turing probabilistică cu aceste proprietăți: XQX rulează întotdeauna în timp polinomial în dimensiunea de intrare XQX dacă răspunsul corect este nu, returnează întotdeauna no XQX dacă răspunsul corect este da, apoi returnează da cu probabilitate de cel puțin 1/2.cu alte cuvinte, algoritmului i se permite să răstoarne o monedă cu adevărat aleatorie în timp ce rulează. Singurul caz în care algoritmul poate returna da este dacă răspunsul real este da; prin urmare, dacă algoritmul se termină și produce da, atunci răspunsul corect este cu siguranță da; cu toate acestea, algoritmul se poate termina cu nu, indiferent de răspunsul real. Adică, dacă algoritmul returnează nu, ar putea fi greșit.Unii autori numesc această clasă R, deși acest nume este mai frecvent utilizat pentru clasa limbilor recursive.Dacă răspunsul corect este da și algoritmul este rulat de n ori cu rezultatul fiecărei rulări independent statistic de celelalte, atunci va reveni da cel puțin o dată cu probabilitate de cel puțin 1 − 2−. Deci, dacă algoritmul este rulat de 100 de ori, atunci șansa ca acesta să dea un răspuns greșit de fiecare dată este mai mică decât șansa ca razele cosmice să corupă memoria computerului care rulează algoritmul. În acest sens, dacă este disponibilă o sursă de numere aleatorii, majoritatea algoritmilor din RP sunt extrem de practice.

vezi mai multe „