Rp randomiseret polynomisk tid er kompleksitetsklassen af beregningskompleksitetsteori, problemer, som der findes en probabilistisk Turing-maskine med disse egenskaber: Karr det kører altid i polynomisk tid i inputstørrelsen Karr hvis det korrekte svar er nej, returnerer det altid Karr, hvis det korrekte svar er ja, returnerer det ja med Sandsynlighed mindst 1/2.med andre ord får algoritmen lov til at vende en virkelig tilfældig mønt, mens den kører. Det eneste tilfælde, hvor algoritmen kan returnere ja, er, hvis det faktiske svar er ja; derfor, hvis algoritmen afslutter og producerer ja, så er det korrekte svar bestemt ja; algoritmen kan dog afslutte med nej uanset det faktiske svar. Det vil sige, hvis algoritmen returnerer nej, kan det være forkert.Nogle forfattere kalder denne klasse R, selvom dette navn er mere almindeligt anvendt til klassen af rekursive sprog.Hvis det korrekte svar er ja, og algoritmen køres n gange med resultatet af hver kørsel statistisk uafhængig af de andre, vil den returnere ja mindst en gang med Sandsynlighed mindst 1 − 2−. Så hvis algoritmen køres 100 gange, er chancen for, at den giver det forkerte svar hver gang, lavere end chancen for, at kosmiske stråler ødelagde hukommelsen på computeren, der kører algoritmen. I denne forstand, hvis en kilde til tilfældige tal er tilgængelig, er de fleste algoritmer i RP meget praktiske.

se mere “