動機
具有有界錯誤的隨機算法,必須在接受概率與拒絕概率之間保持一道可見的間隙。倘若接受概率僅僅略高於二分之一,差距無限小,但其正負號保證正確,情況又如何?複雜度類 PP 所研究的正是這種情形。透過計算接受路徑的數目,可把定義精確化,並說明為何一般的抽樣無法自動在多項式時間內判定如此微小的差異。
本單元中的所有概率均針對固定輸入 。多項式時間隨機機器使用相互獨立的均勻隨機位元。透過以未使用的位元作填充,我們可以假設:對於每個長度為 的輸入,機器恰好讀取 個隨機位元,其中 為取整數值的某個固定多項式。每個隨機串的概率均為 ,即使有多個隨機串導致完全相同的計算歷史亦然。在概率計算中,必須計算隨機串的數目,而非相異計算歷史的數目,這一點至關重要。
嚴格多數與路徑計數
若存在多項式時間隨機機器 ,使得
則稱語言 屬於 。嚴格不等號是定義的一部分。對於否例,接受概率可以恰好等於 。機器不必與 之間存在任何反多項式大小的間隙;在使用 個隨機位元時,接受概率的最小正變化量可以是 。
對於固定輸入,令
則 。PP 條件即 ;當 時,則直接按概率不等式理解。整數 計算的是接受的隨機串,包括機器已作填充但並未檢視的隨機串。
例題 5.2.1
(在此約定下,平局屬於否例)
設某機器使用三個隨機位元。若它在八個隨機串中的五個上接受,則其接受概率為 。若它在四個上接受,則概率恰為 ,因此嚴格多數謂詞的答案為否。若它在三個上接受,答案同樣為否。若把約定由 改為 而不處理平局,則該特定機器所識別的語言可能改變。
常見錯誤
(多數不一定是穩健的多數)
接受概率為 雖然高於 ,但其優勢可以是指數級地小。基於常數間隙及多項式個獨立樣本的 BPP 式證明,不能簡單地照搬。PP 只是規定精確概率位於閾值的哪一側;它並不斷言存在能夠有效估計該正負號的實驗。
見證計數與閾值謂詞
在見證形式的表述下,若存在多項式 及確定性多項式時間謂詞 ,使得
則稱函數 屬於 。較短長度的訊息可借助無歧義的長度約定,編碼為固定長度的字串。見證計數是非負整數,而非判定位元。把非確定性機器的分支規範化為此見證形式,是標準的背景等價結果;我們直接採用上述形式。
命題 5.2.2
(PP 即見證計數上的閾值)
語言 屬於 PP,當且僅當存在以 個見證位元表示的 函數 ,以及某個多項式時間可計算的填充約定,使得
證明
(證明)
給定一台使用 個隨機位元的 PP 機器,取 為以 作為其隨機串來模擬該機器。若 可以為零,則附加一個未使用的隨機位元。附加操作使隨機串的總數及接受的隨機串數目均加倍,從而保持該比例是否嚴格大於二分之一不變。所得的計數屬於 ,並滿足上述閾值條件。
反過來,給定上述見證謂詞,自 中均勻抽取 ,並恰在 時接受。接受概率為 ,它恰在 上大於二分之一。抽樣與驗證均只需多項式時間。填充約定對每個輸入長度統一確定長度,並不改變嚴格閾值。
例題 5.2.3
(在已聲明的變量列表上計算賦值)
對於 ,四個賦值中有三個滿足該公式。因此均勻抽取一個賦值時,接受概率為 ,高於二分之一。對於 ,恰有兩個賦值滿足它,形成平局。所聲明的列表至關重要:加入一個未使用的變量,會使計數與賦值總數同時加倍,比例不變。加入變量,與在分母固定不變的情況下僅僅改變所宣稱的計數,並非同一種操作。
例題 5.2.4
(相差一個接受串的間隙)
設 。一台在 個隨機串中的 個上接受的機器,其概率為 。另一台在 個串上接受的機器則恰為平局。當 隨輸入長度以多項式增長時,相差一個串便產生指數級小的概率間隙。原則上,精確計數可以立即區分這兩種情形,而小規模的經驗抽樣卻很容易在兩種情形下看起來毫無分別。
NP 與有界錯誤隨機計算
定理 5.2.5
(NP 與 BPP 均包含於 PP)
且 。
證明
(證明)
對於 BPP,取一台有界錯誤判定器,其在是例上的接受概率至少為 ,在否例上至多為 。這些概率位於 的正確兩側,因此同一台機器便是一台 PP 機器。
對於 NP,設 驗證長度為 的見證。獨立抽取一個公平位元 及一個均勻的 位元串 。若 ,則立即接受。若 ,則恰在 時接受。當不存在見證時,接受概率恰為 。當至少存在一個見證時,第二個分支貢獻一個正數量,因此接受概率嚴格大於 。即使在指數多個見證中只有一個有效,此構造仍為多項式時間。因此,嚴格閾值能正確區分這兩種情形。
例題 5.2.6
(一個見證即可使精確多數傾斜)
設有八個候選見證,且恰有一個通過驗證者。在由 NP 到 PP 的構造中,立即接受分支貢獻八個接受的數對 ,驗證分支再貢獻一個,因此十六個隨機串中有九個接受。若不存在見證,則十六個串中恰有八個接受,形成平局。該構造並不定位見證;它把見證的存在性編碼於一個微小概率差的正負號之中。
這兩個包含關係都不能證明 PP 擁有有效的有界錯誤算法。NP 的構造可能只有指數級小的優勢,而 BPP 的包含關係也只是單向的。這些類之間已知或被猜想的分離,需要額外的論證;本文並不斷言任何一項。
嚴格多數的補集
僅僅翻轉 PP 機器的輸出,並不足以得到其語言的補集,原因就在平局。
反例模式
對調輸出得不到 PP 語言的補集
假設有人聲稱,對調 PP 機器 的接受與拒絕輸出,便得到識別 補集的機器。取一個輸入 , 在其上使用一個隨機位元 ,並恰在 時接受。它在 個隨機串中的 個上接受,概率恰為 ,故 。對調後的機器恰在 時接受,同樣是 個串中的 個,按嚴格多數規則它也拒絕 。因此 既不在 中,也不在對調後機器的語言中,後者便不是 的補集。修補方法是把平局移到接受的一側,下面的構造正是這樣做。
下面的填充構造在不假設任何間隙的情況下,解決了這一邊界問題。
定理 5.2.7
(PP 對補集封閉)
若 ,則其補集亦屬於 PP。
證明
(證明)
填充原有的 PP 機器,使其使用 個隨機位元。記 ,並令 為其在 上接受的隨機串數目。再加入兩個獨立的隨機位元 ,並沿用 位元串 。按以下四種情形定義新機器:
- 若 為 或 ,則恰在原機器對 拒絕時接受。
- 若 ,則一律接受。
- 若 ,則恰在 時接受。
總共有 個等可能的隨機串。前兩種情形貢獻 個接受的隨機串,第三種貢獻 個,最後一種貢獻一個。因此新機器在 個隨機串上接受。其嚴格多數條件為
由於 為偶數且 為整數,此不等式恰在 時成立。這正是原機器並不以嚴格大於二分之一的概率接受的條件。所有額外的檢驗與模擬都只需多項式時間,因此新機器在 PP 中識別補集。
證明透視
多出來的那一個接受串起甚麼作用
原計數 每改變一,新計數 就改變二。項 與 把閾值恰好定在 :新計數等於 (即平局),恰當 。最後一種情形再加一個接受串;一小於步長二,所以它只在平局 時改變結果,把平局變為接受,而使其他每個非平局的 仍處於原來的一側。填充至 使 為偶數,因此平局值 是整數,確實可能出現。若沒有這個額外的串,構造便重現簡單對調的失敗;若額外加三個或以上的接受串,則 (原機器的是例)也會被接受。
例題 5.2.8
(檢驗邊界情形)
取 且原計數 。補集構造在 個隨機串中有 個接受,因此其接受比例嚴格多於一半。若 ,則新計數為 中的 ,按 PP 的約定,它拒絕。額外的那一個接受串化解了平局;若只是反轉每個原有答案,則在第一種情形中,八個串仍然只有 個接受。
概念視角代數
PP 是帶符號和的正負號
對每個隨機串 ,若 接受就賦值 ,拒絕就賦值 ,並令 。於是 恰當 ,所以 PP 問的是一個整數和的正負號,平局即 。在這個形式下,補集構造就是恆等式 :由於 為偶數, 恰當 。
由補集封閉性及 NP 的包含關係,同樣有 。補集封閉性確立了 ,但並不確立 ,後者仍是一個獨立的問題。
確定性空間上界
精確計數可能需要指數時間,卻仍只使用多項式空間。依字典序枚舉每一個可能的隨機串,在該隨機串上模擬多項式時間機器,並以二進位計數器記錄接受串的數目。枚舉的索引需要 個位元,計數至多需要 個位元。一次模擬因只需多項式時間,故只用多項式空間,而其工作空間可於下一個隨機串時重複使用。
命題 5.2.9
(PP 包含於多項式空間)
。
證明
(證明)
對於輸入 ,計算共同的隨機串長度 ,並以一個 位元計數器枚舉全部 個隨機串。在每個隨機串上分別模擬該 PP 機器,每當它接受時,便使一個 位元的接受計數器加一。最後將計數與 比較,或為統一處理 ,將計數的兩倍與 比較。工作帶儲存兩個計數器以及一次多項式空間的模擬,其大小均為 的多項式。該算法在指數多次模擬之後終止,因此它在多項式空間內判定該語言;此枚舉並不能推出任何多項式時間的上界。
例題 5.2.10
(計數器可以很短,而枚舉可以很長)
當 個隨機位元時,共有 個隨機串。索引需要 個位元,接受計數器需要 個位元,儘管機器可能需要進行超過一百萬次模擬。當 時,同樣的計數器長度仍為多項式,而被模擬的隨機串數目卻是 。空間可以重複使用;時間則不斷累積。
計數觀點能證明與不能證明的內容
矩陣的積和式、其在指定歸約概念下的 -完全性,以及關聯多項式層級與計數的 Toda 定理,都是更深入的重大結果,本文並不證明。完全性的陳述必須指明所採用的歸約及輸入編碼;涉及計數函數的神諭陳述,同樣必須指明如何傳回計數以及如何計費。上述簡單的閾值刻畫,不應被誤當作對這些更深結果的證明。
與上文一樣,可以在多項式空間內枚舉全部見證來計算 計數,但結果可能有指數多個可能的取值,並需要適當的輸出約定。反過來,僅知道計數是否非零,只是 NP 式的判定問題,一般而言所揭示的資訊少於精確計數。計算見證的數目、判定見證是否存在,以及與一半作比較,是三項不同的任務,即使它們使用同一個驗證者亦然。
練習與解答
快速檢查
(某機器使用四個隨機位元,並在八個隨機串上接受。它在此輸入上是否滿足嚴格的 PP 閾值?)
把接受概率與 比較。
解答 · 答案
否。共有十六個隨機串,接受概率為 ;定義要求嚴格不等式。
快速檢查
(在由 NP 到 PP 的構造中,若不存在見證,接受概率是多少?若至少存在一個見證,又有何改變?)
分開考慮構造的兩個分支。
解答 · 答案
若無見證,則恰為 。至少有一個見證時,驗證分支增加一個正概率,使概率嚴格大於 。
快速檢查
(若某 PP 機器使用 個位元,並在 個隨機串上接受,則補集構造接受多少個隨機串?)
利用計數 ,其中 。
解答 · 答案
此處 ,因此計數為 ,總數為 。由於 ,原機器位於否的一側,而補集位於是的一側。
快速檢查
(為何翻轉機器的輸出無法處理平局?)
平局在翻轉之後是甚麼樣子?
解答 · 答案
若原機器恰在一半的隨機串上接受,則其翻轉後的輸出同樣恰在一半的隨機串上接受。在嚴格多數的定義下,兩者的答案都是否。
快速檢查
(為所有 個隨機串編製索引並計算接受的隨機串數目,需要多少空間?)
分別計算索引與計數器的位元數。
解答 · 答案
索引需要 個位元,計數至多需要 個位元;多項式空間的模擬則對每個隨機串重複使用。
快速檢查
(PP 包含於 PSPACE 是否蘊含多項式時間的模擬?)
比較依次進行的步驟數與所用空間。
解答 · 答案
否。該構造可能枚舉指數多個隨機串。多項式空間所限制的是同時儲存的量,而非依次進行的步驟數。