隨機性可以令算法運行得更快,同時不會使其給出錯誤答案。這類算法偶爾可能需要遠較平常為長的時間,因此最壞情況時間界並非恰當的度量。另一種做法則堅持固定的時間上限,並容許算法回答「未知」。這兩種觀點引出複雜度類 ZPP,並說明它與單邊隨機判定程序之間的關係。
我們考慮語言 ,並假設隨機位元是獨立且均勻地抽取的。以下所有概率與期望的陳述,均是針對每個固定輸入 而言;不假設任何輸入分佈。隨機機器的運行時間 計算所有步驟,包括產生隨機位元。多項式期望時間界的意思是:存在同一個多項式 ,使得對每個輸入 皆有 。 可將 增大,使得對每個 都有 。
零錯誤與可變運行時間
定義 1.2.1
(Las Vegas 判定器與 ZPP)
語言 的 Las Vegas 判定器,在每一條終止的計算路徑上都輸出正確的成員資格位元,對每個輸入以概率 1 停機,並且在每個輸入上具有多項式期望運行時間。我們把具有此類判定器的語言所成之類定義為 。「期望」一詞並不保證所有路徑都在多項式時間內完成。該界必須對每個固定長度的所有輸入一致成立。概率為零的無限隨機序列不影響幾乎必然終止,但機器停機的每一條有限路徑上,答案都必須正確。
例題 1.2.2
(重複擲公平硬幣及其運行時間)
考慮一個程序:重複擲一枚公平硬幣,直至首次出現正面,然後返回一個預先確定的正確答案。設 為擲硬幣的次數。對 ,事件 表示前 次均為反面,其概率為 。恆等式 逐點成立;對其非負各項取期望,得 。該程序以概率 1 停機,但對每個固定的 ,需要多於 次擲幣的概率 皆為正。假想中的無限全反面序列概率為零。這個玩具程序用以說明資源上的區別;它的答案是事先給定的,因此並不是針對任意語言的算法。
常見錯誤
(多項式期望時間不等於多項式截止)
期望所約束的,是同一輸入上隨機選擇的平均值,它容許偶爾出現很長的運行。反過來說,一部總是很快停機、但有時給出錯誤答案的機器,並不會自動成為零錯誤機器。運行時間與正確性是兩項獨立的要求;輸出「未知」既不是「是」的答案,也不是「否」的答案。
定義 1.2.3
(RP 與 coRP)
我們亦使用標準的單邊類。若存在多項式時間的隨機判定器,對「是」實例以至少 的概率接受,並且從不接受「否」實例,則語言 屬於 RP。若其補語言屬於 RP,則 屬於 coRP:coRP 判定器從不拒絕「是」實例,並以至少 的概率拒絕「否」實例。所有隨機選擇與概率界,均是針對給定輸入上機器的硬幣而言。重複進行獨立試驗,可以降低所容許的單邊錯誤概率,而不會在另一邊產生錯誤。
例題 1.2.4
(辨識單邊保證的方向)
假設某語言的隨機多項式時間測試,對真實例以概率 接受,對假實例以概率零接受。這是一個 RP 程序:接受即證明屬於該語言,而拒絕則可能不具結論性。以全新的硬幣運行兩次,只要其中一次接受便接受,則在真實例上的假陰性概率至多為 ,而且仍然沒有假陽性。若兩次運行重複使用相同的硬幣,它們的失敗便可能完全相同,平方的論證亦就不成立。
把期望時間轉化為「未知」答案
關鍵估計是 Markov 不等式。對非負隨機變量 與 ,有 。我們以下列形式使用它,並直接證明此形式,而不是引入某個集中不等式定理。
命題 1.2.5
(非負運行時間的截止)
若非負隨機變量 具有有限期望,且 ,則 。
證明
(以示性函數比較證明 Markov 不等式)
逐點而言,。取期望得 。除以正數 即得該界。只要期望有限,無論運行時間分佈的可能取值集合是有限還是無限,此結論皆成立。
例題 1.2.6
(截斷可變時間的判定器)
假設某個正確的隨機判定器在長度為 的輸入上,期望運行時間至多為 。在 步後令其停止(如有需要,截止步數向上取整),若它尚未停機,則輸出「未知」。由 Markov 不等式,到達截止點仍無結果的概率至多為 ;關於在最後一步停機的具體約定,只會改善此界。新程序總是在多項式步數內停機;每當輸出一個位元時,該答案皆正確;並且以至少 的概率給出該答案。檢查截止點的時間只增加多項式的額外開銷。
此截止使用的是屬於 Las Vegas 機器存在性證明的某個特定多項式界。算法無須由單次執行推斷自身的期望運行時間。不同的構造可以內置不同的多項式界,而有限多個較小的輸入長度可以藉增大多項式來處理。
兩個單邊程序給出零錯誤
定理 1.2.7
(零錯誤的刻畫)
。
證明
(兩個方向各自的模擬)
首先假設 ,並取一個期望時間至多為 的 Las Vegas 判定器。將它運行 步。為了得到 RP 判定器,僅當模擬已停機並在截止前返回「是」時才接受;否則拒絕。「否」實例從不被接受,因為任何返回的答案皆正確。對於「是」實例,由截止估計,正確的「是」答案以至少 的概率出現,超過所需的 。所需時間為多項式。
對於 coRP 判定器,使用同一個有界模擬,但僅當它已停機並返回「否」時才拒絕;否則接受。它從不拒絕「是」實例,並以至少 的概率拒絕「否」實例。因此 同時屬於兩個類。這兩個變換把「未知」映射到相反的答案,因為所容許的錯誤位於相反的兩邊。
反過來,假設 有 RP 判定器 與 coRP 判定器 。在每一輪中,以全新的隨機位元運行 。若 接受,則輸出「是」。若它拒絕,則以全新的隨機位元運行 ;若 拒絕,則輸出「否」。否則以獨立的硬幣開始新一輪。 與 的每次運行皆需多項式時間。
對於「是」實例, 從不拒絕,而 在每一輪中以至少 的概率接受。到達第 輪的概率至多為 ,期望輪數至多為 。對於「否」實例, 從不接受,而 在每一輪中以至少 的概率拒絕,故得到相同的尾部界與期望界。該程序只有在 證實「是」時才可能輸出「是」,只有在 證實「否」時才可能輸出「否」,因此從不輸出錯誤答案。它幾乎必然終止,並具有多項式期望時間,從而證明 。
證明透視
兩個單邊類如何互相提供證書
兩個方向各依賴一個想法。對於 ,不顯然的一步是:同一個截斷模擬可以給出兩個不同的判定器,區別只在「未知」被送到哪一邊:對 RP 是拒絕,對 coRP 是接受。這樣做是安全的,因為返回的位元必然正確,所以唯一可能的錯誤就是「未知」的結果,而每個錯誤都落在該類所容許的一邊;Markov 截止把它們的概率限制在 。反方向則是: 只能證實「是」, 只能證實「否」,而循環只在得到證書時才輸出,所以無論硬幣怎樣落下都不會輸出錯誤的位元。概率只在終止性上起作用:每一輪都使用全新的硬幣,使給定過去後失敗的概率至多為 ,從而得到尾部 。若只有 ,「否」實例永遠得不到證書,循環便可能永不停止,這就是兩個類都需要的原因。
每一輪中 與 的次序屬於實現上的選擇,並不改變證明。關鍵在於:「是」證書不可能出現在「否」實例上,「否」證書不可能出現在「是」實例上,而且每一輪都有固定的正概率產生適當的證書。尾部界使用各輪之間全新的獨立隨機性;若無此條件,重複的失敗便可能保持完全相關。
例題 1.2.8
(固定輸入上的一對單邊程序)
設想在某個特定的「是」實例上, 以概率 接受,而 則如可靠性所要求的那樣總是接受。零錯誤程序在 首次成功運行時返回「是」,而且從不返回「否」。需要多於三輪的概率為 ,期望輪數為二。在「否」實例上,角色互換: 總是拒絕,而 的拒絕結果提供正確的「否」答案。這些數值只是對單一輸入說明證明;要證明類的成員資格,則須有一對在每個輸入上都滿足保證的多項式時間算法。
有界時間的表述
把上述想法打包為這樣一個算法,往往較為方便:它輸出「是」、「否」或「未知」,總是在多項式時間內運行,從不輸出錯誤的位元,並且在每個輸入上以至少 的概率輸出一個位元。這樣的算法可給出 ZPP 判定器:運行獨立的副本,直至其中一個返回位元。若每次試驗至多需要 步,則失敗多於 次的概率至多為 ,因此總期望時間至多為 加上多項式的設置時間。所有返回的位元皆正確,而且幾乎必然終止。
反過來,Markov 截止構造可把任何 ZPP 判定器轉化為這樣的有界時間三輸出算法,其成功概率至少為 。這是兩種表述之間的等價,並附有明確的逐輸入成功保證。若某程序在某個輸入上可能永遠輸出「未知」,或只是在選定的輸入分佈上平均而言才成功,則不符合所述定義。
命題 1.2.9
(零錯誤蘊涵有界錯誤)
,且 。
證明
(兩次獨立運行)
第一個包含關係可由上述刻畫得出。對於 RP,獨立運行判定器兩次,只要至少一次運行接受便接受。對「否」實例,接受概率為零;對「是」實例,失敗概率至多為 。這符合通常的 BPP 門檻。對於 coRP,獨立運行兩個副本,只要至少一個拒絕便拒絕;對稱的論證給出至多 的錯誤。這些包含關係並沒有確立任何一個類互不相同,或等於 。
常見錯誤
(正確性並不約束時間)
一部機器可以在每次停機時都輸出正確的位元,但仍不是 ZPP 判定器:例如,它可能在某個輸入上以概率 無限循環,或者幾乎必然停機但期望運行時間為無限。定義同時要求幾乎必然終止與多項式期望界。同樣,該多項式期望必須對給定長度的每個輸入成立,而不是僅在對輸入取平均之後成立。
反例模式
幾乎必然終止並不給出多項式期望時間
一個誘人的說法是:只要一部正確的機器在每個輸入上以概率 1 停機,它的期望運行時間就已經有限,因而有多項式界。設運行時間是取正整數值的隨機變量 ,對 有 。這些概率之和為一,因為 ,部分和逐項相消,所以 以概率 1 為有限。然而
因此期望不可能有任何多項式界。ZPP 的定義於是把期望界與幾乎必然終止分開要求。此例並不聲稱存在針對此分佈的高效抽樣算法。
練習與解答
快速檢查
(某非負運行時間的期望至多為 。求該運行時間至少為 的概率之上界。)
在截止命題中取 。
解答 · 答案
由 Markov 不等式,。
快速檢查
(若每次獨立重複中,產生「未知」的試驗成功的概率皆至少為 ,求連續三次失敗的概率之上界。)
獨立試驗的失敗概率相乘。
解答 · 答案
由獨立性,概率至多為 。
快速檢查
(為甚麼由零錯誤模擬構成的 RP 判定器在超時時要拒絕?)
RP 判定器容許在哪一邊出錯?
解答 · 答案
超時並不具結論性。RP 容許「是」實例以有界概率被拒絕,但從不容許「否」實例被接受;超時時拒絕符合這個方向。
快速檢查
(為甚麼 RP/coRP 構造的每一輪都需要全新的隨機帶?)
想一想給定前面各輪後,一輪失敗的條件概率是多少。
解答 · 答案
獨立而全新的隨機帶使每一輪失敗的條件概率至多為 ,從而得到幾何尾部。若重複使用同一條隨機帶,同一個失敗結果可能永遠重複出現。
快速檢查
(若某零錯誤機器幾乎必然停機,但在某個輸入上的期望時間為無限,它是否滿足這裏所用的 ZPP 定義?)
比較定義中的兩項要求。
解答 · 答案
不滿足。僅有幾乎必然終止,並不能提供所需的多項式期望時間界。
快速檢查
(等式 是否證明了 ?)
這個等式把哪個類等同於交集?
解答 · 答案
不能。該等式只是把交集等同於 ZPP,本身並沒有說明兩個單邊類是否重合。