Loading AI tools
来自维基百科,自由的百科全书
在複雜度理論內,RP("隨機多項式時間")是一個有關概率圖靈機的複雜度類[1],並且存在以下特性:
RP演算法(單次操作) | ||
---|---|---|
產生的答案 | ||
正確 解答 |
是 | 否 |
是 | ≥ 1/2 | ≤ 1/2 |
否 | 0 | 1 |
RP演算法(n次操作) | ||
產生的答案 | ||
正確 解答 |
是 | 否 |
是 | ≥ 1 − 2−n | ≤ 2−n |
否 | 0 | 1 |
co-RP演算法(單次操作) | ||
產生的解答 | ||
正確 解答 |
是 | 否 |
是 | 1 | 0 |
否 | ≤ 1/2 | ≥ 1/2 |
換句話說,這個演算法允許在操作的時候進行全然概率的猜測。這個演算法會回傳YES的狀況必然是輸入為真的狀況;因此如果這個演算法說了YES,那我們就知道了這個輸入必定為是:不過,這個演算法可以在不管正確解答為何的時候回傳NO。也就是,如果這個演算法回傳答案是錯的,可能是這個演算法犯錯了(也就是其實這個輸入應該是對的)。
有一些作者叫這一個複雜度類R,不過這個名字更常被使用於定義包含了所有遞歸語言的複雜度類。
如果輸入的答案為"是"且這個演算法運作了n次,每次跑出來的答案統計上獨立於其他答案,那回傳起碼一次YES的概率則至少有1 − 2−n這麼多。所以如果這個演算法跑了夠多的次數,那數學上來說他回傳錯誤解答的概率就會變得非常非常小,甚至小過運算的電腦被宇宙射線影響因此錯誤的概率。在這個概念上,如果我們有一個夠好的亂數來源,大多數的RP演算法都是非常具有實做價值的。
這裏選用的1/2這個常數,是不需要太嚴格的一個選擇:無論我們將定義裏面的1/2換成任何小於1的非零常數,RP這個集合仍舊包含了所有原來的問題。(這裏的常數代表說此數字跟輸入沒有任何關係)
RP的定義告訴我們,如果RP演算法說答案是YES,則答案一定為"是":如果說是NO,則"通常"答案會是"非"。複雜度類co-RP的定義方式類似,不過是說答案是NO的時候,則答案一定是非,說答案是YES的時候答案則"通常"為是。換句話說,RP演算法接受了所有的YES狀態,而接受或者拒絕了一部分的NO狀態。BPP這個複雜度類形容的演算法則是在YES狀態跟NO狀態都有可能犯錯的演算法,因此它同時包含了RP和co-RP。
RP與co-RP的交集則叫做ZPP。
如同RP有時候被叫做R,有一些作者使用co-R而非co-RP。
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的子集合。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.