ZPP (複雜度)
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此條目沒有列出任何參考或來源。 (2023年1月28日) |
在計算複雜度理論內, ZPP(zero-error probabilistic polynomial time,零錯誤概率多項式時間)是一個與概率圖靈機有關的的複雜度類,並且存在以下特點:
- 這機器永遠會給出正確的"是"或者"否"的答案。
- 這個機器平均運作的時間是多項式時間以內。
換句話說,有一個演算法會在運作時使用一個完美隨機的硬幣,並且永遠回傳正確的答案(這種演算法被稱作拉斯維加斯演算法(Las Vegas algorithm))。對一個輸入大小為n的問題,存在一個多項式p(n),令平均的運作時間小於p(n)(有可能偶爾會超過)。
另外,ZPP可以定義為一個問題的集合,裏面每個問題都存在一個可以解決此問題的概率圖靈機,且此機器性質如下:
- 運轉時間永遠是多項式時間
- 會回傳YES,NO或者DO NOT KNOW的答案
- 答案如果不是DO NOT KNOW,就會是正確的答案
- 如果問題的正確答案是YES,這機器回傳YES的概率至少是1/2(其他時候回傳DO NOT KNOW)
- 如果問題的正確答案是NO,這機器回傳NO的概率至少是1/2(其他時候回傳DO NOT KNOW)
以上這兩個定義是相等的。 ZPP的定義是基於概率圖靈機。其他基於概率圖靈機的複雜度類包含了BPP和RP。至於BQP (複雜度)這個複雜度類則換成使用了量子電腦這種也是具有隨機性的電腦。
以交集定義
ZPP這個複雜度類正好完全相等於RP和Co-RP這兩個類別的交集。這也是一個常用的ZPP的定義。為了展示這個定義,首先得注意同時在'RP和co-RP的每個問題均有個拉斯維加斯演算法,如下:
- 假設我們有一個由RP演算法A和(可能完全不同的)co-RP演算法B辨識的L語言。
- 給一個輸入到L裏面,讓A演算輸入。如果傳回「是」,則答案一定是「是」。而讓B演算輸入,如果傳回「否」,答案必是「否」。如果兩者皆未發生,則重複這一步驟。
注意到只有一部機器會給出錯誤答案,而兩部機器在回答時給出錯誤答案的概率幾乎是50%。
證據與證明
與其他複雜度類的關聯
既然ZPP = RP ∩ coRP,ZPP自然包含在RP和coRP裏面。
複雜度類P包含在ZPP裏面,有一些人猜想P = ZPP,換句話說,所有的拉斯維加斯演算法都有一個等同的決定型多項式時間演算法。
如果證明了ZPP = EXPTIME(雖然這猜想幾乎是不可能的)將代表P ≠ ZPP,因為P ≠ EXPTIME(參見時間譜系理論)。
外部連結
|