Rp satunnaistettu polynomiaika on laskennallisen kompleksisuusteorian kompleksiluokka, ongelmia, joille todennäköisyyslaskennallinen Turingin kone on olemassa näillä ominaisuuksilla:⁕se kulkee aina polynomiajassa tulokoossa⁕jos oikea vastaus on ei, se aina palauttaa NO⁕jos oikea vastaus on kyllä, niin se palauttaa Kyllä todennäköisyydellä vähintään 1/2.toisin sanoen algoritmi saa heittää ajon aikana todella satunnaista kolikkoa. Ainoa tapaus, jossa algoritmi voi vastata kyllä on, jos todellinen vastaus on kyllä; jos algoritmi siis päättyy ja tuottaa kyllä, niin oikea vastaus on ehdottomasti kyllä; algoritmi voi kuitenkin päättyä ei riippumatta todellisesta vastauksesta. Toisin sanoen, jos algoritmi palauttaa ei, se voi olla väärässä.Jotkut kirjoittajat kutsuvat tätä luokkaa R, vaikka tätä nimeä käytetään yleisemmin rekursiivisten kielten luokasta.Jos oikea vastaus on kyllä ja algoritmi ajetaan n kertaa jokaisen suorituksen tuloksella tilastollisesti riippumaton muista, niin se palaa kyllä ainakin kerran todennäköisyydellä vähintään 1-2 -. Joten jos algoritmi suoritetaan 100 kertaa, niin todennäköisyys, että se antaa väärän vastauksen joka kerta on pienempi kuin mahdollisuus, että kosmiset säteet turmelivat algoritmia ajavan tietokoneen muistin. Tässä mielessä, jos satunnaislukujen lähde on käytettävissä, useimmat RP: n algoritmit ovat erittäin käytännöllisiä.

Katso lisää ”