RP (複雜度)

在複雜度理論內，RP（"隨機多項式時間"）是一個有關機率圖靈機的複雜度類^[1]，並且存在以下特性：

RP演算法（單次操作）
	產生的答案
正確解答	是	否
是	≥ 1/2	≤ 1/2
否	0	1
RP演算法（n次操作）
	產生的答案
正確解答	是	否
是	≥ 1 − 2⁻ⁿ	≤ 2⁻ⁿ
否	0	1
co-RP演算法（單次操作）
	產生的解答
正確解答	是	否
是	1	0
否	≤ 1/2	≥ 1/2

此演算法的運行時間不超過一個以輸入長度為自變量的多項式函數
如果輸入的答案為非，此演算法會回傳NO
如果輸入的答案為是，則回傳YES的機率至少1/2（其餘的機率則是回傳NO）。

換句話說，這個演算法允許在操作的時候進行全然機率的猜測。這個演算法會回傳YES的狀況必然是輸入為真的狀況；因此如果這個演算法說了YES，那我們就知道了這個輸入必定為是：不過，這個演算法可以在不管正確解答為何的時候回傳NO。也就是，如果這個演算法回傳答案是錯的，可能是這個演算法犯錯了（也就是其實這個輸入應該是對的）。

有一些作者叫這一個複雜度類R，不過這個名字更常被使用於定義包含了所有遞歸語言的複雜度類。

如果輸入的答案為"是"且這個演算法運作了n次，每次跑出來的答案統計上獨立於其他答案，那回傳起碼一次YES的機率則至少有1 − 2⁻ⁿ這麼多。所以如果這個演算法跑了夠多的次數，那數學上來說他回傳錯誤解答的機率就會變得非常非常小，甚至小過運算的電腦被宇宙射線影響因此錯誤的機率。在這個概念上，如果我們有一個夠好的亂數來源，大多數的RP演算法都是非常具有實做價值的。

這裡選用的1/2這個常數，是不需要太嚴格的一個選擇：無論我們將定義裡面的1/2換成任何小於1的非零常數，RP這個集合仍舊包含了所有原來的問題。（這裡的常數代表說此數字跟輸入沒有任何關係）

與P和NP的關聯

P是RP的子集，而RP是NP的子集。相同的，P也是co-RP的子集，而co-RP則是co-NP的子集。我們尚未知道這一些是否是嚴格子集（也就是說，這一些集合是否相等或不相等）。然而，一般我們相信P = BPP這個推測是真實的，這樣一來的話RP，co-RP，P就全部都是相等的了。如果我們又假設P ≠ NP的話，這就代表說RP嚴格包含於NP（也就是RP ≠ NP）。我們還不知道是否RP = co-RP，抑或是否RP是NP和co-NP的交集的子集合，不過這些都可以由P = BPP這件事情推論出來。

一個比較自然的例子確定此問題在co-RP裡面但是尚不知道是否在P裡面的是等同多項式檢定，此問題決定給予的多變量整數多項式是否等於一個零多項式。舉例來說, x·x - y·y - (x + y)·(x - y)是一個零多項式，而 x·x + y·y則不是。

另一種有時候比較好使用的RP的定義是能夠被非決定型圖靈機解決問題的集合。此機器接受答案，若且唯若至少有常數比例條計算路徑（此常數與輸入長度無關）回傳解答為"是"。另一方面NP則只需要一條路徑回傳答案為是，這件事實使我們針對同一個問題可以建立比較少的路徑。因此，此特徵顯示出RP顯然是NP的子集合。

參考文獻

^ David, Matei; Pitassi, Toniann. Separating NOF communication complexity classes RP and NP. arXiv:0802.3860 [cs]. 2008-02-26 [2023-02-09]. doi:10.48550/arXiv.0802.3860. （原始內容存檔於2023-02-09）.

[1] David, Matei; Pitassi, Toniann. Separating NOF communication complexity classes RP and NP. arXiv:0802.3860 [cs]. 2008-02-26 [2023-02-09]. doi:10.48550/arXiv.0802.3860. （原始內容存檔於2023-02-09）.

[1]

RP (複雜度)

目次

相關複雜度類

與P和NP的關聯

相關參閱

參考文獻