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