ZPP

ZPP（Zero-error Probabilistic Polynomial）可以被定義為機率圖靈機的一類問題。

基本介紹

• 外文名：Zero-error Probabilistic Polynomial
• 縮寫：ZPP

交點定義

ZPP類正好等於RP和co-RP的交集。這通常被認為是ZPP的定義。為了說明這一點，首先要注意的是，RP和co-RP中的每個問題都有拉斯維加斯算法，如下所示：

a.假設我們有一種語言L被RP算法A和（可能完全不同的）co-RP算法B所識別。
b.給定L中的輸入，在輸入上運行A一步。如果返回YES，則答案必須為YES。否則，在輸入上運行B一步。如果它返回NO，答案必須是NO。如果兩者都不出現，請重複此步驟。

請注意，只有一台機器可能會給出錯誤的答案，並且在每次重複過程中機器給出錯誤答案的機會最多為50%。這意味著達到第k輪的機會在k中呈指數下降，表明預期的運行時間是多項式的。這說明RP相交co-RP包含在ZPP中。

為了證明RP中包含了ZPP與co-RP相交，假設我們有拉斯維加斯算法C來解決問題。然後我們可以構造下面的RP算法：

運行C的時間至少是預期運行時間的兩倍。如果它給出了答案，請給出答案。如果在我們停止之前沒有給出答案，請給NO.

根據馬爾可夫的不平等，在我們停止之前它會得出答案的機會至少是1/2。這意味著我們可以通過停止並產生NO，在YES實例上給出錯誤答案的機會最多為1/2，符合RP算法的定義。 co-RP算法是相同的，只是如果C“逾時”它會給出YES。

見證和證明

類NP，RP和ZPP可以根據集合中的成員證明來考慮。

定義：一個集合X的驗證者V是一個圖靈機，這樣：

a.如果x在X中，則存在一個使得V（x，w）接受的字元串w;
b.如果x不在X中，則對於所有的字元串w，V（x，w）拒絕。

字元串w可以被認為是會員證明。 在可以有效驗證的短期證明（長度受輸入大小的多項式約束）的情況下（V是一個多項式時間確定性圖靈機），字元串w被稱為見證。

注釋：

該定義非常不對稱。 x在x中的證明是單個字元串。 x不在X中的證明是所有字元串的集合，其中沒有一個是成員證明。

證人的可用性是統一的。 對於X中的所有x，必須有證人。 情況並非如此，X中的某些x太難以驗證，而大多數則不是。
證人不一定是傳統的解釋證據。 如果V是一個機率圖靈機，如果x在X中，它可能接受x，那么證明是一串硬幣翻轉，它通過運氣，直覺或天才引導機器接受x。
共同概念是非會員身份的證明，或補充集中的成員資格。

類NP，RP和ZPP是具有成員證人的集合。 NP級只要求證人存在。他們可能非常罕見。在2f（| x |）可能的字元串中，對於f多項式，只有一個需要導致驗證者接受（如果x在X中。如果x不在X中，則沒有字元串會導致驗證者接受）。

對於RP和ZPP類，隨機選擇的字元串可能是證人。

相應的共同班級見證了非會員資格。特別是，co-RP是一類集合，如果x不在X中，任何隨機選擇的字元串都可能是非隸屬關係的見證。 ZPP是任何隨機字元串可能是X中的x的見證者，或者x不在X中的集合的類別，這種情況可能是這樣。

將此定義與RP，co-RP和ZPP的其他定義相結合很容易。機率多項式時間圖靈機V * w（x）對應確定性多項式時間圖靈機V（x，w），用V的第二個輸入帶代替V *的隨機帶，硬幣翻轉。通過選擇見證作為隨機字元串，驗證者是一個機率多項式時間圖靈機，當x在X中時接受x的機率很大（大於1/2），但是如果x∉X（對於RP ）;如果x∈X（對於co-RP），當x不在X時拒絕x很大但是為零;並且正確地接受或拒絕x作為X的成員是大的，但是不正確地接受或拒絕x（對於ZPP）。

通過反覆隨機選擇一個可能的見證者，隨機串作為見證的大機率給出了一個期望的多項式時間算法來接受或拒絕輸入。相反，如果圖靈機是期望的多項式時間（對於任何給定的x），那么相當一部分運行必須是多項式時間有界的，並且在這樣的運行中使用的投幣序列將是證明。