RP (複雜度)

複雜度理論內,RP("隨機多項式時間")是一個有關機率圖靈機複雜度類[1],並且存在以下特性:

RP演算法(單次操作)
產生的答案
正確
解答
≥ 1/2 ≤ 1/2
0 1
RP演算法(n次操作)
產生的答案
正確
解答
≥ 1 − 2n ≤ 2n
0 1
co-RP演算法(單次操作)
產生的解答
正確
解答
1 0
≤ 1/2 ≥ 1/2
  • 此演算法的运行时间不超过一个以输入长度为自变量的多项式函数
  • 如果輸入的答案為非,此演算法會回傳NO
  • 如果輸入的答案為是,則回傳YES的機率至少1/2(其餘的機率則是回傳NO)。

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

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

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

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

相關複雜度類

RP的定義告訴我們,如果RP演算法說答案是YES,則答案一定為"是":如果說是NO,則"通常"答案會是"非"。複雜度類co-RP的定義方式類似,不過是說答案是NO的時候,則答案一定是非,說答案是YES的時候答案則"通常"為是。換句話說,RP演算法接受了所有的YES狀態,而接受或者拒絕了一部分的NO狀態。BPP這個複雜度類形容的演算法則是在YES狀態跟NO狀態都有可能犯錯的演算法,因此它同時包含了RPco-RP

RPco-RP的交集則叫做ZPP

如同RP有時候被叫做R,有一些作者使用co-R而非co-RP

與P和NP的關聯

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

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

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

相關參閱

参考文献

  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).