傳統的驗證者可以讀取整份證書。概率可驗證證明(probabilistically checkable proof)可以遠長於被檢查的部分:驗證者使用少量隨機位元選取少數位置,然後判斷所見的位元在局部上是否一致。值得注意的並不是真斷言存在證明,而是假斷言的每一個所謂證明,都會以不可忽略的概率通不過隨機選取的檢驗。這個區別把驗證誤差轉化為最優化間隙。
局部存取與整體正確性
定義 10.1.1
(概率可驗證證明驗證者)
概率可驗證證明驗證者是一部具有隨機存取二進位證明字串的隨機化多項式時間機器。對於長度為 的輸入,其隨機性預算限制它所使用的公平隨機位元數目,其查詢預算限制它所讀取的證明位置數目。除非明確聲明採用非適應性慣例,後續查詢所選取的位置可以取決於先前的回答。完備性指每個肯定實例都有一個以指定的高概率被接受的證明;可靠性指否定實例的每個證明被接受的概率至多為指定的較低概率。
證明在隨機硬幣被選取之前已經固定。它可以取決於輸入,但不能在得知哪些位置被查詢後才選擇新的值。否則驗證者所面對的是一個適應性的證明者,而不是檢查一份固定的證明。在可靠性條件中,並不假設證明是誠實的。一個正確的論證必須對每個可能的證明字串,包括那些沒有編碼任何有意義賦值的字串,界定其被接受的概率。
對於 個隨機位元和 次查詢,記號 描述在固定的完備性與可靠性常數下相應的驗證者類,通常取完美完備性及至多為 的可靠性。驗證者的時間為多項式,位址的長度亦為多項式。當隨機位元數為 時,可能的隨機字串只有多項式個;若查詢次數為常數,則每個字串只選取常數個位置。隨機存取是一個明確的資源慣例:把實體紙帶讀寫頭移動到遠處的位置,並不會被當作驗證者擁有循序紙帶那樣計費。
命題 10.1.2
(消除常數次查詢的自適應性)
設 是對每個輸入和隨機字串至多進行 次二進制查詢的驗證者。則存在一個非自適應驗證者 ,使用相同的隨機位元及至多 次查詢,並且對每個固定證明的接受概率與 完全相同。若 為常數,則 亦為常數。
證明
(展開查詢樹)
固定輸入和驗證者的隨機字串。若它至多進行 次二進制查詢,可能的查詢與答案歷史構成一棵至多有 個查詢節點的二叉樹。非自適應驗證者可以計算這棵樹中出現的所有位置,一次讀取這些位置,再用答案模擬原來的路徑。重複位置都從同一個固定證明中一致地讀取。構造這棵樹只用驗證者的程式碼、輸入及其固定隨機字串,不依賴某個候選證明。模擬時捨棄與實際讀到的答案不一致的分支。當 是常數時,新的查詢上界仍是常數,且對每個固定證明的接受概率不變。
證明透視
查詢樹由甚麼構成
論證的關鍵在於這棵樹由甚麼構成。它只用驗證者的程式碼、輸入和固定的隨機字串,所以對每個證明都是同一棵樹;因此可以在讀取任何證明位元之前就寫下全部位置,也因此對每個固定證明分別保持接受概率不變。捨棄與答案矛盾的分支,是使模擬忠實的步驟,因為真正的路徑只有一條。代價是樹的大小: 為常數時 也是常數,所以容許自適應不會改變常數查詢類;但它隨 指數增長,所以同一轉換未必能保持隨輸入增長的查詢預算。
為何單靠抽樣並不足夠
在這個抽樣實驗中,取 個布爾(Boolean)約束,其中 是整數。均勻選擇一個約束恰好使用 個公平位元;任意 的精確均勻抽樣則需要額外的實現論證。考慮對這些約束提出的一個賦值。驗證者可以均勻地選取一個約束,讀取其中的變量,並在該約束被滿足時接受。若賦值滿足每一個約束,則必定接受。若它違反了比例為 的約束,則拒絕概率恰好為 。只有當每個候選賦值都至少違反固定正比例的約束時,這項檢驗的可靠性才至多為 。
概念視角組合
把非適應性驗證者看成一族約束
設檢驗是非適應性的,並使用 個隨機位元。每個隨機字串 便指定至多 個證明位置和作用在它們上的一個謂詞,即一個約束 。對固定的證明 ,接受概率恰好是 所滿足的約束佔全部 個約束的比例。可靠性說明:當實例為假時,沒有證明能滿足超過某個固定比例的約束,這就是關於約束的間隙陳述。
例題 10.1.3
(一個被違反的子句可能難以察覺)
對整數 取 ,再取互相矛盾的一對單文字子句 與 ,再加上 個恆真子句 的副本。此公式不可滿足。然而, 的任一取值都恰好滿足其中一個矛盾子句以及所有填充子句,因此均勻隨機的子句檢驗只以概率 拒絕。隨著 增大,該概率趨向於零。僅憑不可滿足性並不能提供常數的可靠性間隙。
例題 10.1.4
(一個具有真正間隙的小型公式)
考慮四個子句 、、 與 。對 的四個賦值,每一個都恰好違反其中一個子句,因此該公式不可滿足,且每個賦值的值均為 。無論所提供的賦值為何,均勻選取的子句被違反的概率都是 。若對同一個固定賦值進行三次獨立選取的檢驗,且要求三次全部通過,則接受概率為 。這個例子具有常數間隙,但它並沒有展示如何把每個不可滿足的公式轉換為具有常數間隙的公式;那是困難的一般構造。
PCP 構造改變了證明的表示方式和檢驗,使假斷言無法被做到與所有局部檢驗近乎一致。一個證明位元可以描述冗餘的編碼資訊,而不是某一個原有的變量。挑戰在於僅憑局部視野來強制整體一致性;單單在任意證書上加上隨機抽樣,並不能解決這項挑戰。
作為所述依賴的 PCP 定理
定理 10.1.5
(PCP 定理,標準形式)
在上述隨機存取與多項式時間的慣例下,,其中完備性為完美,可靠性至多為 。
我們不加證明地陳述此定理中較困難的方向。它構造出一個可局部檢驗的編碼,以及具有所承諾間隙的檢驗。反方向的包含關係有一個有用的初等解釋:多項式時間驗證者只讀取多項式長度的位址,因此當隨機字串只有多項式個而查詢次數為常數時,證明可以用其相關的、多項式個被查詢的位元來表示。NP 機器猜測這些位元並檢查所有隨機字串,恰好在其接受比例達到驗證者的完備性門檻時接受。完整形式化的版本必須處理適應性查詢,方法是納入沿著所有可能的查詢與回答路徑所到達的每個位置;常數的查詢上限使每個隨機字串只剩下常數條這樣的路徑。定理本身遠比這個計數觀察深刻。
常見錯誤
(把定理誤讀為還原證明)
此定理並不是聲稱驗證者可以由少量位元還原整份證明。隨機性使不誠實的證明很可能通不過檢驗;接受是關於所聲稱實例之正確性的一項概率保證。某一次特定的隨機檢驗可能接受假的實例,而可靠性上界容許這種情況。
由間隙到近似問題
定義 10.1.6
(3-CNF 公式的值與最優值)
對於具有 個子句的 3-CNF 公式,每個子句至多含三個文字(較短子句可用重複文字填充),把賦值的值定義為它所滿足的子句比例,並令 為最大的此類比例。最大值取遍對所有變量的賦值,而實際賦值的值可在多項式時間內計算。可滿足的公式其最優值為 ;不可滿足的公式其最優值可以接近 ,正如填充的例子所示。
我們不加證明地使用 PCP 困難性的下列間隙形式。
定理 10.1.7
(PCP 困難性的間隙形式)
存在固定的有理常數 及一個多項式時間歸約,把每個 3-CNF 公式 映到一個 3-CNF 公式 ,使得:若 可滿足,則 可滿足;若 不可滿足,則每個賦值至多滿足 中 比例的子句。
任何正間隙都可減弱為這樣的有理間隙,使門檻成為可計算常數。這是一個額外的非平凡定理,並非僅僅抽樣原有子句的結果。此構造及其與 PCP 定理的關係不屬本單元的範圍。
命題 10.1.8
(間隙排除了多項式近似方案)
假設所述的間隙定理以及 。則不存在用於最大化 3-CNF 公式所滿足子句比例的多項式時間近似方案。在此,方案必須對每個固定的 ,在多項式時間內回傳一個實際賦值,其滿足至少 。
證明
(藉區分兩種情況的證明)
假設存在這樣的方案。固定常數 ,並使用其對此值的多項式時間算法。給定一個 3-SAT 公式,構造間隙歸約的輸出 並運行近似算法。計算所回傳賦值所滿足的子句比例。
若原公式可滿足,則 ,因此所回傳的賦值其值至少為 。若原公式不可滿足,則每個賦值(包括所回傳的賦值)其值至多為 。由於 ,把該值與嚴格介乎兩者之間的門檻比較,即可在多項式時間內判定 3-SAT。由 3-SAT 的 NP 完全性(此處不加證明地使用),這將蘊含 ,與假設相矛盾。
此定理並不斷言 MAX-3SAT 沒有有用的近似算法。它在所述假設下排除的是一族能任意接近最優值的算法。它也沒有說每一個 3-CNF 實例都困難:該歸約為必須處理所有實例的統一算法建立了最壞情況下的障礙。
例題 10.1.9
(一個數值間隙判定)
僅作說明,假設某個歸約的間隙為 。以 運行的方案,在肯定輸出上會得到至少 的值,而在否定輸出上每個賦值的值至多為 。門檻 區分了這兩種情況。這個數值例子說明了證明;它並不聲稱所引用定理的常數恰好是 。
常見錯誤
(接近最優的值並不是精確答案)
對於任意不可滿足的公式,近似算法可能輸出極接近 的值;可滿足的公式也可能因為算法只是近似而得到小於 的值。上述判定程序之所以有效,是因為歸約製造了固定的間隙,並且所回傳賦值的值可以被檢查,而不是因為近似自動判定了可滿足性。
隨機性、放大與固定證明
若驗證者獨立地重複一個常數查詢的檢驗,並在任何一次檢驗拒絕時拒絕,則一次運行中至多以概率 被接受的假證明,在 次獨立運行後被接受的概率至多為 。完美完備性仍然保持完美。查詢次數增加為原來的 倍,隨機位元數亦同樣增加;對於固定的 ,PCP 定理中的兩個漸近上界仍然是 與 。這項計算分別適用於每個固定的證明。它並不容許證明在觀察到驗證者的硬幣之後才改變。
例題 10.1.10
(重複局部一致性檢驗)
假設假實例的每個證明通過一次檢驗的概率至多為 。三次獨立檢驗只有在三次全部通過時才接受該證明,其概率至多為 。被每次檢驗都接受的正確證明,其被接受的概率仍然是 。
下面的例子說明,各次重複必須相互獨立。
反例模式
重用同一個隨機字串不算放大
斷言:用同一個隨機字串把檢驗重複三次,假證明的接受概率就從 降到 。取一個只用一個隨機位元 的驗證者,以及假實例的一個固定證明 ,它在 時通過檢驗、在 時失敗,所以恰以概率 被接受。若三次重複都用同一個 ,它們恰在 時一起通過,接受概率仍是 ,而不是 。斷言不成立,因為各次重複完全相關。修正:每次重複都抽取新的隨機位元,共三個;三次檢驗便相互獨立,全部通過的概率為 。
練習與解答
快速檢查
(在上述填充的矛盾公式中,計算所滿足子句比例的最優值。)
數一數一個賦值至多能滿足多少個子句。
解答 · 答案
每個賦值都違反兩個矛盾子句之一,並滿足另一個以及全部 個重言式。因此最優值為 。
快速檢查
(為何近似證明要計算所回傳賦值的值,而不是相信近似算法所提供的數值聲稱?)
想想可靠性陳述針對的是甚麼。
解答 · 答案
間隙的可靠性適用於實際的賦值。計算輸出的值可以證實其真實的值,並確保即使算法所報告的數字有誤,它也不會超過否定情況下的最優值。
快速檢查
(在數值間隙例子中,為何僅有 的近似比率不能得出所述的門檻論證?)
把肯定輸出的保證值與否定輸出的最優值比較。
解答 · 答案
在肯定輸出上,保證只會是 ,這低於否定情況的上界 。兩個範圍重疊,因此僅憑該保證不能區分兩種情況。
快速檢查
(解釋為何 PCP 證明在驗證者選定其隨機查詢位置之後不能被更改。)
回想可靠性界所量化的對象。
解答 · 答案
可靠性界定的是每個固定證明在驗證者的隨機硬幣上被接受的概率。若所謂的證明可以在看到查詢之後作出適應性的回應,則模型及其量詞將會不同,所述的 PCP 保證便不適用。