一份簡短的證書是一個靜態對象。對話則容許驗證者在收到資訊之後,另行選擇全新的挑戰。這個挑戰必須如此設計:誠實的證明者能夠回應,而不誠實的證明者卻無法充分預測它,以致無法令虛假的宣稱具說服力。圖非同構提供了一個具體例子:驗證者可以有效率地生成一個經偽裝的圖,即使它並不知道如何單憑自身辨認該圖的來源。
兩個角色與兩種概率
定義 9.1.1
(語言的互動證明)
一個互動證明系統包含一個在多項式時間內運行的隨機化驗證者 ,以及一個沒有計算時間限制的證明者 。它們就共同輸入 交換訊息,最後驗證者接受或拒絕。對於語言 ,完備性要求:存在某個證明者,使 對每個 以至少 的概率接受。可靠性要求:對每個證明者, 對每個 以至多 的概率接受。概率取自驗證者的隨機選擇;若證明者使用隨機性,亦取自證明者的選擇。類別 由具有此類多項式時間驗證者、且訊息數目為多項式個的語言所組成。
量詞各有不同的作用。完備性容許針對整個語言選定一個誠實的證明者,而不是驗證者可以執行的有效率算法。可靠性則是對抗性的:它必須對每一種可能的證明者策略都成立。驗證者的計算以及整個交談記錄的總長度必須受多項式限制;證明者則可以為了決定發送何種訊息而解決計算上困難的問題。為防範惡意證明者,驗證者至多讀取規定的多項式訊息長度再加一位;訊息過長時拒絕。在評估成功概率時,輸入是固定的。這是最壞情況的要求,而不是對各圖對取平均。
非確定性證書是這幅圖像的特例:證明者發送一份證書,驗證者以確定性方式檢查。只有當驗證者的私有選擇影響所需的回應時,互動才有用。公開通訊並不意味著對證明者隱藏的選擇必須在使用之前被揭露。
作為單訊息對話的證書
此定義已經包含與非確定性驗證的一個有用比較。與其把證明者當作一個無從解釋的神諭,不如證明這個包含關係:NP 見證給出證明者的訊息,而確定性驗證者仍然負責最終決定。
命題 9.1.2
(NP 包含於 IP)
中的每個語言都有一個具完美完備性與完美可靠性的互動證明,該證明使用一則證明者訊息及一個確定性多項式時間驗證者。
證明
(證明)
為所給的 NP 語言選取一個多項式時間驗證者 及多項式證書長度界限。證明者發送一份候選證書;若它過長,互動驗證者即拒絕,否則在輸入及該證書上計算 。若輸入屬於該語言,則某份短證書會被接受,所以誠實的證明者發送它,接受是必然的。若輸入不屬於該語言,則無論證明者採用何種策略,都沒有證書會被接受,因此拒絕是必然的。驗證者使用多項式時間。這證明了該包含關係;它並沒有證明每個互動證明都有一份簡短的靜態證書。
例題 9.1.3
(小型團的證書)
假設輸入圖的頂點為 ,邊為 ,而所宣稱的團大小為 。證明者發送列表 。驗證者檢查各項是否為互不相同的頂點,然後對照輸入檢查三對 ;全部都是邊,所以接受。若該圖沒有大小為 的團,則每個可能的三頂點列表不是重複了某個頂點,就是包含一條缺失的邊。可靠性的論證針對所有可能的訊息,而不僅是誠實證明者碰巧發送的那份列表。
圖同構與重新標號
定義 9.1.4
(圖同構與圖非同構)
兩個有限簡單圖 與 若存在其頂點之間的一個雙射,同時保持鄰接與非鄰接關係,則稱它們同構。當兩者都有 個頂點時,我們可以將各頂點集標號為 ;對這些標號作一個置換,便得到一個重新標號的圖。圖非同構(此處簡稱 GNI)是由互不同構的有限簡單圖對所組成的語言。
頂點數目不同的圖對顯然非同構,可以立即接受,所以下面的協議針對的是大小相等的圖。大小為零的圖對由兩個空圖組成,因此是同構的;驗證者可以立即拒絕。
證明者看見兩個圖。驗證者選取一個均勻隨機的位元 ,以及獨立且均勻隨機的、作用於 個標號上的置換 ,發送 ,並詢問它來自哪一個輸入圖。若答案等於 ,驗證者便接受。為了有效率地實現均勻置換,可使用標準的隨機置換程序;下面的概率論證則採用理想的均勻選擇。從公平位元作有界誤差的實現,需要小心處理精確取樣的問題,亦可改用精確度足夠的多項式時間取樣器,並在可靠性界限中計入其誤差。
例題 9.1.5
(路徑還是三角形?)
設 為三個頂點上的路徑, 為三角形。重新標號改變頂點的名稱,但不改變邊的數目。路徑恆有兩條邊,而三角形有三條邊,所以即使是驗證者,也可以透過數邊來辨認來源。這說明了協議中的各則訊息,不過一般協議的重點在於:對於任意的輸入圖,有效率的驗證者並不需要知道任何簡單的區分不變量。
在有界運行時間內對置換取樣
理想的均勻置換使主要想法易於看清,但一個使用固定數目公平位元的多項式時間驗證者必須實際實現其選擇。在大小不是二的冪的範圍內,一般而言無法從固定數目的公平位元精確產生均勻隨機整數。因此,我們明確地控制近似誤差。
命題 9.1.6
(有界位元取樣器接近均勻)
對每個正整數 ,存在一個取樣器,它使用多項式個公平位元並在多項式時間內運行,其在 個對象的置換上的輸出分佈,與均勻分佈的總變差距離至多為 。
證明
(藉耦合各個選擇來證明)
使用常見的交換構造:對於 ,從 中選取一個索引,並將其與當前位於位置 的項目交換。若這些選擇相互獨立且均勻,則 個選擇序列各自的概率為 ,並給出互不相同的置換,所以輸出是均勻的。
設 為使 的最小整數。為了在大小為 的範圍內選取索引,抽取 個公平位元以形成從 至 的均勻整數,取其對 的餘數,再加 。每個索引出現的次數是 的下取整或上取整。其概率與 相差少於 ,所以這個單一選擇與均勻分佈的總變差距離至多為 。將該選擇與理想的均勻選擇耦合,使它們不一致的概率至多為 。在所有步驟上,聯集界給出不一致的概率至多為 。若沒有任何一步不一致,則輸出的置換一致。因此輸出分佈的總變差距離在 以內。該取樣器至多使用 個位元及多項式時間。
對於同構的圖對,將實際的取樣器與理想的取樣器耦合。針對任何固定的證明者策略,只要所取樣的置換一致,互動記錄與接受結果便一致。成功猜中的理想概率為 ,所以實際概率至多為 。耦合可以在任何先前交談記錄的條件下重新進行。因此,兩個全新回合的可靠性至多為 ,而完備性仍為 。這證明該協議符合固定公平位元模型,而無需假設存在精確的非二進制隨機選擇。
完備性:誠實的證明者能夠辨認軌道
假設 與 不同構。 的重新標號 與 同構,而不可能與另一個輸入圖同構:否則,兩個同構的複合將顯示 。無計算限制的證明者可以枚舉置換,並判定哪一個圖與 同構。它確定地返回 。因此該協議對非同構的輸入具有完美完備性。
「無計算限制」這個詞確有實質作用。誠實的證明者可以檢視全部 個置換;我們並不假設存在進行此搜尋的多項式時間算法。驗證者只是對置換取樣、重新標號該圖,並將一位元的答案與其私有位元作比較。
可靠性:挑戰隱藏了其來源
命題 9.1.7
(單回合圖非同構協議)
對於大小相等的輸入圖,上述協議在誠實證明者之下以概率 接受每個非同構的圖對。若輸入圖同構,則在理想均勻取樣器之下,任何證明者,無論多麼強大,只要它總是發送一個位元,被接受的概率恰為 。此處所述的有界位元實現及重複,給出了 GNI 的一個互動證明。
證明
(為何同構的圖給出相同的分佈)
設 ,其中 為某個固定的置換。若 ,則所發送的圖為 。若 ,則為 。乘以固定置換 是有限置換群上的雙射,所以只要 均勻分佈, 亦均勻分佈。因此, 的分佈對 的兩個取值是相同的。
證明者看見輸入及 ,但 並沒有提供關於公平位元 的任何資訊。對於基於該視野的任何固定回應規則,回應等於 的概率為 。對證明者的任何私有隨機性取平均後,結論相同。非位元的回應可以直接被拒絕,此時概率至多為 。
證明透視
為何挑戰不帶任何資訊
不明顯的一步,是比較整個有標號圖的分佈,而不是邊數之類的不變量。假設 恰好只用在一處:它把 時的挑戰變成 。乘以固定的 是置換群上的雙射,所以均勻的 仍然均勻,兩個挑戰分佈因而相同。另有兩項要素同樣重要。置換 與位元 是獨立選取的,因此 的分佈不依賴於 ,就表示 與 獨立。而且 在證明者作答之前一直保密,所以證明者的回答是 、輸入及其自身隨機性的函數,這些都不依賴於 ;它與 相符的概率恰好是 。
整個論證無須對證明者的運行時間作任何限制。若 不均勻,兩個 的分佈便可能不同,論證即告失效;若 被揭露,回答就成了 的函數,論證同樣失效。
這個論證是資訊論意義上的:並無使用對不誠實證明者運行時間的任何限制。重要的等式是有標號圖的整個分佈之間的等式,而不僅是邊數或任何單一圖不變量之間的等式。即使許多置換產生同一個有標號圖,乘以 也會把在兩種情況下產生該圖的置換配成對,其重數保持不變。
反例模式
沒有隨機重新標號,挑戰會洩露其來源
假設驗證者省去置換,直接發送 。取 ,令 只有一條邊 , 只有一條邊 。這兩個圖是同構的,同構由互換 與 的置換給出,因此該輸入不屬於 GNI。然而作為有標號圖,它們並不相同,所以看見 的證明者可以立即讀出 ,並以概率 被接受。可靠性證明需要均勻的 :重新標號之後,無論所發送的圖來自哪一個輸入,它的分佈都相同。
重複與適應性策略
在理想均勻取樣之下,獨立地運行兩次挑戰,並僅在兩個答案均正確時接受。完備性仍為 ,而可靠性至多為 ,低於所需的 。作弊的證明者可以利用整個先前的交談記錄來選擇下一個回應。然而,在該交談記錄的條件下,下一個位元與置換是全新的,新挑戰的兩個條件分佈仍然相同。其條件成功概率至多為 。將兩個條件界限相乘得到 ;同樣地, 個回合給出的可靠性至多為 。
若驗證者在證明者作答之前就揭露 ,這個論證便會被破壞。挑戰圖是公開的,但隨機的來源位元在回應之前保持私有。把這兩項資訊分開,是核心的設計選擇。
例題 9.1.8
(重新標號的副本沒有給出關於該位元的證據)
設兩個輸入均為同一個有標號的四圈。某個特定的重新標號 可能由多個置換產生,因為該圈具有對稱性。儘管如此,對於 時產生 的每個置換,相同的置換在 時亦產生 。條件分佈相合,看見 並不會改變任一位元的先驗概率 。對於不同但同構的有標號副本,論證使用固定的重新標號 來得到相同的配對。
常見錯誤
(誠實的證明者不足以證明可靠性)
證明誠實的證明者能夠作答,只是完備性。若圖同構,作弊的證明者可以使用任何策略,包括針對完整交談記錄量身訂造的策略。可靠性的證明必須顯示,沒有任何此類策略能夠從兩個相同的分佈中還原出一個隱藏的位元。
這證明了甚麼,又沒有證明甚麼
該協議證明 GNI 屬於 。它並沒有證明 GNI 不屬於 ,沒有證明圖同構沒有多項式時間算法,亦沒有證明 嚴格大於 。重要定理 需要額外的工具,在此不予證明。這些區分之所以重要,是因為一個包含關係或一個成功的協議是正面的構造;它並不會自動確立複雜度類別之間的分離。
練習與解答
快速檢查
(為甚麼非同構的輸入圖會給出互不相交的可能挑戰圖集合?)
假設有一個圖同時屬於兩個集合。
解答 · 答案
若有一個圖同時屬於兩個集合,它就會與兩個輸入圖都同構。把一個同構與另一個同構的逆複合,會令兩個輸入圖同構,與假設相違。
快速檢查
(假設輸入圖同構。即使證明者具適應性,連續正確回答三個全新獨立挑戰的最大概率是多少?)
把各個條件界限相乘。
解答 · 答案
在理想均勻取樣之下,界限為 :在任何先前的交談記錄之後,下一個全新的挑戰對於任一隱藏位元仍具有相同的分佈。使用上述有界位元取樣器時,相應的界限為 。
快速檢查
(若驗證者把其隱藏位元連同重新標號的圖一併發送給證明者,甚麼會失效?)
想想誰會得知這個位元。
解答 · 答案
證明者可以對每個輸入都返回所提供的位元,包括同構的圖對。驗證者便會以概率 接受虛假的宣稱,違反可靠性。