ZPP複雜度

在計算複雜度理論內, ZPP（zero-error probabilistic polynomial time，零錯誤機率多項式時間）是一個與機率圖靈機有關的的複雜度類。

基本介紹

• 中文名：ZPP複雜度
• 外文名：zero-error probabilistic polynomial time

簡介

在計算複雜度理論內, 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（參見時間譜系理論）。