RP (複雜度) 在複雜度理論內RP隨機多項式時間是一個有關機率圖靈機的複雜度類並且存在以下特性 此演算法的运行时间不超过一个以输入长度为自变量的多项式函数 如果輸入的答案為非此演算法會回傳NO 如果輸入的答案為是則回傳YES的機率至少其餘的機率則是回傳NO 換句話說這個演算法允許在操作的時候進行全然機率的猜測這個演算法會回傳YES的狀況必然是輸入為真的狀況因此如果這個演算法說了YES那我們就知道了這個輸入必定為是不過這個演算法可以在不管正確解答為何的時候回傳NO也就是如果這個演算法回傳答案是錯的可能是這個演算法犯錯了也就是其實這個輸入應該是對的 有一些作者叫這一個複雜度類R不過這個名字更常被使用於定義包含了所有遞歸語言的複雜度類 如果輸入的答案為是且這個演算法運作了n次每次跑出來的答案統計上獨立於其他答案那回傳起碼一次YES的機率則至少有  n這麼多所以如果這個演算法跑了夠多的次數那數學上來說他回傳錯誤解答的機率就會變得非常非常小甚至小過運算的電腦被宇宙射線影響因此錯誤的機率在這個概念上如果我們有一個夠好的亂數來源大多數的RP演算法都是非常具有實做價值的 這裡選用的這個常數是不需要太嚴格的一個選擇無論我們將定義裡面的換成任何小於的非零常數RP這個集合仍舊包含了所有原來的問題這裡的常數代表說此數字跟輸入沒有任何關係