Rp Randomisert polynomisk tid er kompleksitetsklassen av beregningskompleksitetsteori, problemer som en probabilistisk Turingmaskin eksisterer for med disse egenskapene:⁕den kjører alltid i polynomisk tid I inngangsstørrelsen⁕Hvis det riktige svaret ER NEI, det returnerer ALLTID INGEN⁕HVIS det riktige svaret ER JA, så returnerer DEN JA MED sannsynlighet minst 1/2.med andre ord, algoritmen får lov til å vende en virkelig tilfeldig mynt mens den kjører. Det eneste tilfellet hvor algoritmen kan returnere JA er hvis det faktiske svaret ER JA; derfor hvis algoritmen avsluttes OG produserer JA, så er det riktige svaret definitivt JA; algoritmen kan imidlertid avslutte UTEN uavhengig av det faktiske svaret. Det vil si, hvis algoritmen returnerer NEI, kan det være feil.Noen forfattere kaller denne klassen R, selv om dette navnet er mer vanlig for klassen av rekursive språk.Hvis det riktige svaret ER JA og algoritmen kjøres n ganger med resultatet av hvert løp statistisk uavhengig av de andre, vil DET returnere JA minst en gang med sannsynlighet minst 1-2 -. Så hvis algoritmen kjøres 100 ganger, er sjansen for at den gir feil svar hver gang lavere enn sjansen for at kosmiske stråler ødela minnet til datamaskinen som kjører algoritmen. I denne forstand, hvis en kilde til tilfeldige tall er tilgjengelig, er de fleste algoritmer i RP svært praktiske.

se mer »