Rp randomiserad polynomtid är komplexitetsklassen för beräkningskomplexitetsteori, problem för vilka en probabilistisk Turing-maskin finns med dessa egenskaper: sackaros den körs alltid i polynomtid i ingångsstorleken (om det rätta svaret är nej, returnerar det alltid nej kakaros om det rätta svaret är ja, då returnerar det ja med Sannolikhet minst 1/2.med andra ord får algoritmen vända ett verkligt slumpmässigt mynt medan det körs. Det enda fallet där algoritmen kan returnera ja är om det faktiska svaret är ja; därför om algoritmen avslutas och producerar ja, då är det rätta svaret definitivt Ja; algoritmen kan dock avslutas med nej oavsett det faktiska svaret. Det vill säga, om algoritmen returnerar nej, kan det vara fel.Vissa författare kallar denna klass R, även om detta namn oftare används för klassen av rekursiva språk.Om det rätta svaret är ja och algoritmen körs n gånger med resultatet av varje körning statistiskt oberoende av de andra, kommer den att returnera ja minst en gång med Sannolikhet minst 1 − 2−. Så om algoritmen körs 100 gånger, är chansen att den ger fel svar varje gång lägre än chansen att kosmiska strålar skadade minnet på datorn som kör algoritmen. I den meningen, om en källa till slumptal är tillgänglig, är de flesta algoritmer i RP mycket praktiska.

se mer ”