證書(certificate)的選取是為了說服驗證者,而隨機性的選取則是為了使錯誤的證書難以通過驗證。這兩項選擇的先後次序十分重要。若證明者在看到隨機硬幣之前便寫下一則訊息,則該訊息必須經得起其後才選取的隨機測試。若證明者先看到硬幣,則可針對該特定測試度身訂造回應。我們將仔細定義這兩種設定,並證明在經過足夠強的放大(amplification)之後,第一類協議可由第二類協議模擬。
以下所有語言均為 的子集。驗證者是一個確定性的多項式時間算法,接收一個輸入、一則訊息,以及一串獨立均勻的隨機位元。訊息長度與隨機性長度的多項式界限隨驗證者一併固定。證明者在計算上不受限制,但必須遵守訊息長度的界限。為方便閱讀,我們採用完備性(completeness) 與可靠性(soundness);當驗證者的隨機測試彼此獨立時,這些常數可透過放大而更改。
先於隨機測試的訊息
定義 9.4.1
(MA 類)
若存在多項式 及多項式時間謂詞 ,使得對每個長度為 的輸入 均有
則稱語言 屬於 。
較短的訊息可藉填充(padding)與長度分隔符號編碼。訊息的內容在隨機字串被抽樣之前已經固定。「是」與「否」兩個條件均對其各自類型的所有輸入作量化,而不僅限於典型輸入或某個選定的輸入分佈。
例題 9.4.2
(著色證明)
設輸入為一個有限圖,其頂點已明確列出。訊息為每個頂點指派三種顏色之一。驗證者檢查每一條邊,當且僅當其兩端點顏色不同時才接受;驗證者無需使用其隨機位元。對於可 3-著色的圖,必有某則訊息被接受。對於不可 3-著色的圖,每則訊息均必被拒絕。這是一個具有完美完備性與完美可靠性的 MA 協議,由普通的 NP 見證(witness)得出。無效的顏色或格式錯誤的編碼會被拒絕。
命題 9.4.3
(包含於 MA 的基本包含關係)
每個屬於 的語言與每個屬於 的語言均屬於 。
證明
(證明)
對於 NP 語言,以多項式大小的見證作為訊息,並運行確定性的多項式時間驗證者,忽略隨機位元。在「是」實例上,一個可接受的見證其接受概率為一;在「否」實例上,每個見證的概率均為零。
對於 BPP 語言,忽略訊息,並利用驗證者的硬幣運行 BPP 判定器。其成功保證在每個固定輸入上至少為 。特別地,每則訊息的接受概率均相同,故在「否」實例上所有訊息均符合可靠性。如此即得出兩個包含關係,而無需假設 NP 與 BPP 相等,亦無需假設其中一者包含另一者。
先於回應的公開硬幣
定義 9.4.4
(AM 類)
在兩則訊息的公開硬幣 協議中,Arthur 先把隨機字串 傳送給 Merlin;然後 Merlin 傳送 。等價地說,若存在多項式時間謂詞 及多項式訊息與隨機性界限,使得
則語言屬於 AM。
此處 可依賴於已公開的 。由於訊息空間是有限的,事件 等價於存在一個不受限制的回應策略,能在該硬幣字串上成功。可靠性指出,即使是最佳的此類策略,其成功概率至多為 。隨機性是公開的;私有硬幣的互動式協議需要另行定義與分析。
概念視角組合
接受表格的行與列
對固定的輸入,寫出一張接受位元的表格:每個訊息 佔一行,每個隨機串 佔一列。MA 要求存在某一行,其中至少 的項為 (是實例);或要求每一行至多有 的項為 (否實例)。AM 則計算含有至少一個 的列所佔的比例,這個比例須至少為 或至多為 。兩個類別的分別在於:證明者選取的是一整行,還是每一列中的一格。
例題 9.4.5
(為何選擇的先後次序十分重要)
取一個隨機位元 與一個訊息位元 ,並令 當且僅當 時接受。若先固定訊息,則任何一個固定訊息被接受的概率均為 。若先公開隨機位元,則選取 便以概率一成功。這個有限謂詞說明了由 轉變為 的差別;但它本身並不能證明 MA 與 AM 是不同的類。
常見錯誤
(相同的可靠性界限在公開硬幣下未必成立)
假設每個固定訊息騙過某隨機測試的概率至多為 。這並不蘊含「存在某則訊息騙過該測試」的概率至多為 。不同的訊息可在不同的隨機字串上成功。例如,令 與 均為兩位元字串,而測試當且僅當 時接受:每個固定的 通過的概率為 ,但對每個 都有某個 通過,故「存在某則訊息通過」的概率為 。我們必須界定它們成功事件的聯集,或採用另一種論證。下文的證明透過放大,直至對所有可能訊息取聯集界(union bound)成為可負擔為止。
例題 9.4.6
(圖非同構的挑戰)
在以下理想實驗中,給定頂點數相同的兩個圖,Arthur 均勻地選取其中一個,施以均勻隨機的置換,並把所得的圖傳送出去。Merlin 指出所選取的是哪一個原圖。若兩圖不同構,則不受限制的 Merlin 能辨認其同構類,並總能答對。若兩圖同構,則無論選取哪一個,挑戰的分佈均相同,因此任何回應策略的成功概率均不會高於 。獨立重複可使後者的概率降至 以下;分佈與重複的相關論斷,會在另一個互動式證明單元中詳細證明。在此特定協議中,隨機置換只透過挑戰圖而成為公開;這個例子說明了互動式驗證的動機,但其本身並不能確立上述公開硬幣 AM 的定義。
本段首先描述理想的均勻置換實驗。從 個置換精確均勻抽樣,一般不能只用固定有限個公平位元。要得到有界時間的公平位元驗證者,應使用圖非同構單元中已證明的抽樣器:其置換分佈與均勻分佈的全變差距離至多為 。對同構圖及任意證明者策略,單輪成功概率於是至多為 。給定任何先前互動記錄,該界仍成立,因此兩個使用新隨機位元的輪次具有至多 的可靠性錯誤,完備性仍為一。不能把上述理想的 界直接當作近似抽樣器的精確界。
為何 MA 包含於 AM
以下證明採用關於獨立 – 變量的常用 Hoeffding 界:若它們的共同期望值至多為 ,則其平均值達到 的概率至多為 ;而當期望值至少為 時,相應的下尾界同樣成立。我們引用此集中不等式而不加證明。此處的獨立性是針對某一固定訊息的各次重複而言。
定理 9.4.7
(在公開硬幣之前先放大)
。
證明
(證明)
設 ,其驗證者為 ,訊息長度為 。對於輸入長度 ,取 ,並抽取 個獨立的隨機字串 。定義 當且僅當 次計算 中有嚴格多數接受時,接受訊息 。Arthur 在收到 之前,先把全部 個隨機字串傳送出去。它們的總長度以及運行時間均為 的多項式。
若 ,選取一個 MA 見證 ,其原有接受概率至少為 。對於這個固定的見證, 次結果是獨立的。Hoeffding 界給出其接受次數至多為一半的概率至多為 。因此,以高於 的概率,訊息 是有效的;適應性的 Merlin 當然可以傳送它。
若 ,固定某則特定訊息 。其原有接受概率至多為 ,故它通過多數測試的概率至多為 。可能的訊息恰有 個。由聯集界,即使只有一則訊息通過的概率至多為
這恰好就是針對「在看到所有硬幣之後才選取 」的證明者的可靠性條件。我們並未假設不同訊息的成功事件之間相互獨立;聯集界並不需要獨立性。由此得到的公開硬幣協議便證明了此包含關係。
證明透視
為何重複次數必須隨訊息長度增長
證明中三項條件各只使用一次。完備性只用於單一見證 ,所以「是」的情形不需要聯集界。可靠性是逐則訊息應用的,之後才把 個失敗事件相加。唯一不尋常的一步是選取 :每則訊息的誤差 必須勝過訊息的數目 ,而 ,因為 。若 為常數,論證便告失效:取 時界為 ,只要 便超過 ,不能說明任何事。證明得以完成,是因為可靠性是在硬幣之後才量化的:訊息的存在性被吸收進聯集之中,Merlin 針對 度身訂造 的自由,只需付出 這個因子。
驗證者採用嚴格多數,因此平局視為拒絕。在「是」實例上,下尾估計已涵蓋可能出錯的平局;在「否」實例上,上尾估計所界定的是一個更大的、包含平局的事件。因此無需額外的平局裁決隨機性。
放大所需的次數取決於見證的長度。常數次重複雖可降低每個固定訊息的失敗概率,但在硬幣公開之後,仍有指數多個候選訊息可供嘗試。上述線性次數的重複使每個訊息的錯誤指數地縮小,足以抵銷全部 個候選訊息。這是包含關係的證明,並非這兩個類相等或不相等的證明。
放大公開硬幣協議
放大必須遵守訊息的先後次序。在 AM 協議中,Merlin 看到全部公開硬幣,並可在各次重複之間協調其回應。若宣稱 Merlin 依賴於回應的接受事件彼此獨立,則是錯誤的。相反,對於每個隨機挑戰,我們問的是:是否有任何回應能通過該挑戰。這個問題只取決於挑戰本身,因此所得的指示變量在獨立抽樣的各個挑戰之間是獨立的。
命題 9.4.8
(AM 的多項式級小誤差)
設 具有完備性至少為 、可靠性至多為 的公開硬幣 AM 協議。對於任何取非負整數值的多項式 , 具有一個公開硬幣 AM 協議,使其在長度為 的輸入上,兩種錯誤概率均低於 。
證明
(證明)
取 個獨立的隨機字串,並傳送它們的串接。Merlin 為每個字串回傳一個候選回應,驗證者當且僅當各別檢查中有嚴格多數接受時才接受。對每個 ,定義 當且僅當至少存在一個容許的回應能通過第 個隨機字串上的原有檢查。由於 固定且各挑戰獨立,不論 Merlin 如何選擇實際的回應,指示變量 均相互獨立。
在「是」實例上,。對於每個好挑戰佔多數的序列,不受限制的證明者可為每個好挑戰選取通過的回應,故放大後的驗證者接受。在「否」實例上,。無論 Merlin 採用何種聯合回應策略,它都無法使壞挑戰通過,因此要使多數檢查被接受,便需要多數的 為一。Hoeffding 界把任一種錯誤概率界定為 。總通訊量與運行時間仍為多項式。此證明並不要求證明者所選的回應彼此獨立。
例題 9.4.9
(回應可依賴於所有挑戰)
設有兩個公開挑戰字串 。證明者可以同時利用兩個字串來選取其第一個答案,而非僅利用 。若對於 不存在任何容許的答案,這種額外的協調仍不能使第一項檢查通過。因此,答案是否存在的指示變量,為每一種協調策略提供了上界。在放大後的構造中,即使訊息不必獨立,這些指示變量仍是獨立抽樣的。
同樣的區別也出現在包含關係的證明中。在那裏,我們是在抽取一條長隨機帶之後,對訊息取聯集來界定;而在 AM 放大的證明中,我們則為每個獨立挑戰定義一個存在性事件,並界定這些事件的多數。兩種論證都從固定的輸入出發,並保持證明者的完全自由清晰可見。兩者都沒有以「重複必然有效」這種非正式的說法,取代明確的完備性與可靠性量詞。
加入更多回合的公開硬幣與回應,只有在回合數增長時才會改變類別。
通往推廣的路徑
有更多回合時會改變甚麼?
加入更多回合的公開硬幣與回應,只有在回合數增長時才會改變類別。
只有常數個公開硬幣回合的協議,可以重新整理成這裏研究的兩訊息形式,所以定義的是同一個類別 AM。若容許回合數隨輸入長度按多項式增長,類別就變成 PSPACE。這些是在別處證明的標準結果;改變的結構是 Arthur 的硬幣與 Merlin 的訊息之間交替的次數。
練習與解答
快速檢查
(對於等式謂詞 當且僅當 ,計算最佳固定訊息的成功概率,以及硬幣公開後作出回應的最佳概率。)
比較一個固定位元與一個已公開的位元。
解答 · 答案
每個固定的位元與均勻隨機位元相符的概率為 。一旦該位元被公開,選取相同的位元便以概率一成功。
快速檢查
(為何 NP 驗證者在「否」實例上,對每一則可能的訊息都給出 MA 可靠性?)
回想 NP 可靠性對見證的要求。
解答 · 答案
NP 可靠性指出,沒有任何見證能使確定性驗證者接受「否」實例。忽略隨機性後,每則訊息的接受概率均為零。
快速檢查
(在包含關係的證明中,若 ,聯集界中有多少則長度為二的訊息?所示的選取使用多少次重複?)
計算 與 。
解答 · 答案
共有 則訊息。所選取的重複次數為 ;聯集界的上界估計為 ,小於 。
快速檢查
(解釋為何在聯集界論證中,不同訊息的接受事件不必相互獨立。)
在這個實驗中,所有訊息有甚麼共通之處?
解答 · 答案
它們全部都是針對同一串已公開的隨機字串來評估的。因此,一則訊息的成功可能與另一則的成功相關。聯集界只是把各事件個別的概率界相加,在事件之間不獨立時仍然成立。
快速檢查
(若驗證者的隨機字串在訊息之前被公開,可靠性必須界定甚麼?)
對訊息的量詞現在處於哪個位置?
解答 · 答案
它必須界定的是:在公開隨機字串之上,存在任何容許的回應使驗證者接受的概率。這涵蓋每一種回應策略,包括在看到硬幣之後才選取的策略。
快速檢查
( 是否證明 ?)
這證明了哪一個方向的包含關係?
解答 · 答案
不能。該包含關係指出每個 MA 語言都有 AM 協議,但它並沒有證明反向的包含關係,亦沒有給出能區分兩者的語言。