動機
多項式空間機器可以有指數多個組態,因此其整個轉移矩陣太大,多項式時間驗證者無法把它寫出來。關鍵在於:透過索取經仔細挑選的低次數摘要,來驗證單一個矩陣項。反覆平方把一段長的計算歸約為較短的計算,而隨機直線檢驗則避免了每一階段的斷言數目加倍。
我們證明 ,並與量化公式配套單元中所證明的互動式證明之多項式空間上界結合。證明使用求和檢驗協議,以及配套求和檢驗單元中的適應性可靠性定理;同時亦用到階為 的有限域之存在性、在明確表示的有限域中進行多項式時間算術,以及標準的多項式空間機器組態。下文會說明驗證者如何取得合適的明確域。本證明以上述所列名的基礎結果為前提,而不依賴任何未經證明的量子或計數定理。
固定一部判定語言 的確定性多項式空間判定機 ,採用單工作帶、二元工作字母表的模型;標準的模擬與二元編碼保持多項式空間,並作為背景知識使用。對於輸入 ,把其組態編碼為 位元字串,其中 為 的多項式。加入一個接受匯點與一個拒絕匯點,各自帶有自環,並把停機組態導向相應的匯點。加入足夠多的未使用位元,使其在每個有效編碼中均固定為零,從而令有效組態的數目加上兩個匯點少於 。無效的位元字串沒有任何出邊。從真正起始組態可達的每個組態都恰有一個後繼,而機器最終會到達其中一個匯點。
布爾轉移矩陣及其低次數延拓
設 為定義在有限域 上的 矩陣,其項 恰當 為 的指定後繼時等於一,否則為零。令
由於起始組態在每一步都有唯一的後繼, 中以起始組態標示的行恰有一個非零項,其值為一,位於經過 步後所到達的組態。停機的計算在停機前不會重複任何組態,故至時間 時已到達某個匯點。因此
此處用到確定性:一般的非確定性圖可以有許多條路徑,即使存在一條路徑,其數目在模域特徵數後也可能為零。
定義 9.3.1
(轉移矩陣的多重線性延拓)
對於位元字串 ,定義相等指示函數
在布爾(Boolean)點 上,當 時其值為一,否則為零。把每個矩陣延拓為 個變量的多項式:
它在布爾點對上與 一致,且對每個變量的次數至多為一,其總次數至多為 。此表達式含有指數多項,因此對 ,驗證者不會把它展開。
例題 9.3.2
(雙狀態確定性轉移)
對於轉移 、,其布爾矩陣為 。其多重線性延拓就是 :對於任何布爾來源,該項恰當目標位元為一時等於一。把此矩陣平方會得到同一個矩陣。這個微小的例子說明了,多項式如何能在驗證過程中不逐一列出而表示所有矩陣項。
對於局部的組態編碼,基底延拓 可以被有效地計算。採用獨熱的狀態位元與讀寫頭位置位元、二進位的帶格位元,以及為兩個匯點選取的互異固定編碼,而這些編碼落在普通組態編碼之外。在每個有效的普通組態中,完整的狀態及每個完整的讀寫頭模式都是獨熱的,且每個未使用位元均為零。枚舉多項式數目的組合:當前非停機狀態、輸入頭位置、工作頭位置,以及被掃描的工作符號。對每個合法的轉移情形,乘上指示函數,以固定完整的來源與目標之狀態/讀寫頭模式、所有未使用位元,以及被改變的帶格。對於每個不變的帶格,設其來源位元為 、目標位元為 ,採用多重線性相等因子 。每個情形都是一個乘積,其中每個來源或目標位元至多出現在一個因子之中。
從停機組態到標準匯點的轉移另行處理:固定完整的停機來源控制與讀寫頭模式以及未使用的來源位元,但不限制來源的帶位元;再乘上一個指示函數,固定目標的整個匯點編碼。在此情形下不施加不變帶格相等條件,因為標準匯點的帶內容可以不同。每個匯點自環以其完整來源編碼與目標編碼的指示函數之乘積表示。這些停機與匯點情形與非停機情形互不相交,而後者在布爾編碼上彼此互不相交,因為當前狀態、讀寫頭位置與被掃描符號決定了所屬情形。無效編碼不符合任何情形。這個和式有多項式數目的情形,是一個多項式大小的電路,對每個來源與目標位元皆為多重線性,並在布爾點對上與 一致。由布爾立方體上多重線性內插的唯一性,可知它等同於 。
關於唯一性的論斷:若兩個多重線性多項式在每個布爾輸入上一致,則將二者相減,並對變量個數作歸納:把差寫成 ,其中兩個係數均不涉及 。在 與 處求值,使兩個係數在較小的布爾立方體上均為零;由歸納法,它們是零多項式。因此,驗證者可以計算所需的基底延拓,而不僅僅是某個與其在布爾點上取值相同的任意多項式。
例題 9.3.3
(非布爾輸入處的相等性)
在特徵二下,一位的多重線性相等多項式為 。它在布爾數對 處等於一,在 處等於零。然而在 上,,它既不是零也不是一。驗證者在域上的點處計算多項式;它不會假裝每個中間值都是布爾真值。這種行為是預期之內的,也正說明了為何必須指定多重線性延拓。
以求和檢驗處理一次平方步驟
對於位元字串 與域向量 ,指示函數 已於上文定義。當 被域向量 取代時,使用其對 的多重線性內插:
對於 的一個被聲稱的值,矩陣平方恆等式給出
此處在求和期間 為固定的域向量。把該表達式中的布爾字串換成變量向量,並使用 ,便把被加項定義為域變量 的多項式。
命題 9.3.4
(平方被加項的各別變量次數很小)
在 個域變量 中,該被加項對每個別變量的次數至多為二。因此,次數界為二的求和檢驗,把關於 的斷言,歸約為關於該被加項在某個隨機三元組 處的斷言。
證明
(證明)
每個 出現在一個相等指示函數因子中,以及多重線性多項式 中,故次數至多為二。每個 亦然。每個座標 在兩個多重線性矩陣因子中各出現一次,次數同樣至多為二。該恆等式由展開 的定義,並在布爾指標上代入 而得。即使驗證者無法直接展開這個形式上的低次數多項式,求和檢驗定理仍適用於它。
在最後的求和檢驗點,驗證者可以計算兩個相等指示函數因子,但尚未能計算 。它向證明者索取兩個被聲稱的值
並檢驗它們的乘積乘上已知的指示函數因子後,是否等於最後的求和檢驗斷言。這兩個值並不受信任。若在每個平方層級分別驗證它們,會產生一棵二叉的斷言樹,故我們把它們合併為一個斷言。
在隨機直線上合併兩個斷言
設 與 為 中的兩點。證明者送出一個次數至多為 的單變量多項式 ,聲稱
驗證者檢驗 與 ,選取一個新的均勻 ,並遞歸地檢驗單一斷言:。係數列表長於 者一律拒絕。真正的直線限制之次數至多為 ,因為 是 個變量的多重線性多項式。
命題 9.3.5
(隨機直線斷言歸約)
若 中至少有一個為假,且端點檢驗通過,則遞歸斷言仍然為真的概率至多為 。
證明
(證明)
所送出的多項式與真正的直線限制,其次數均至多為 。若某個端點值為假而端點檢驗通過,則兩個多項式在該端點處不同,因而並不恆等。它們之差為非零多項式,在 中至多有 個根。證明者在看到新的均勻 之前已選定 ,因此即使以整個先前的對話記錄為條件, 等於真值的概率至多為 。
例題 9.3.6
(直線上的假端點)
對於 上的玩具多重線性多項式 ,設 、。真正的直線限制為 。若證明者虛假地聲稱第二個端點值為三,則任何滿足 的 都與 不同。若容許的次數為二,其差至多在兩個域元素處為零。隨機挑戰或許會錯過某個特定的錯誤,但在所述次數界之下,它不可能在每一個挑戰處都掩蓋假端點。
完整的驗證協議
驗證者從斷言 開始,對 依次施行平方求和檢驗,再施行隨機直線歸約。在第零層,它直接計算 的多項式大小電路。所有證明者訊息都明確檢驗其次數界。
定理 9.3.7
(多項式空間語言具有互動式證明)
。
證明
(證明)
選取大小 的域。取得明確域的一個確定性方法是:選取 ,枚舉次數為 的二元首一多項式,直至找到一個不可約者,並以枚舉所有可能的首一因子來檢驗候選者。至多有 個候選者,且至多有 個可能因子,故此暴力構造對 為多項式時間。每個正整數次數的不可約多項式之存在性,源自有限域的構造及乘法生成元的存在性;這些事實已在有限域配套單元中證明。該商環表示 ,支持多項式時間算術,而均勻的 位元字串可抽樣出均勻的域元素。
若 ,所有被聲稱的值皆可誠實地選取。布爾起始項為一,每個矩陣恆等式與每次求和檢驗皆精確成立,而直線限制通過兩個端點及每個挑戰。驗證者以概率一接受。
若 ,則初始斷言為假。在層級 ,求和檢驗使用 個變量及各別次數二,故其適應性可靠性論證把一個假的和式斷言變成真的最終被加項斷言之概率,界定為至多 。若最終斷言仍為假,但證明者的乘積檢驗通過,則 中至少有一個必為假:因為若兩者皆正確,其乘積與已知的指示函數將給出被加項的真值。若某個指示函數因子為零,則一個非零的假最終斷言根本無法通過該檢驗。
在有假端點的情況下,直線歸約定理界定下一個遞歸斷言變為真的概率至多為 。以每一個先前的對話記錄為條件,在此層級逃離假斷言的概率因此至多為 。共有 個層級。對「假斷言首次變為真的層級」使用聯集界,得總概率至多為 。若沒有發生這樣的逃離,驗證者的直接基底計算會予以拒絕。因此,對於否例,任何證明者被接受的概率至多為 。
共有 個層級,每層有 輪求和檢驗與一次直線檢驗。次數為二的訊息有三個係數,直線訊息至多有 個係數。所有域算術、基底計算、通訊與隨機位元的產生,均使用多項式資源。證明者不受限制,能夠計算指數大的矩陣項及誠實訊息的係數。這就是 的一個互動式證明。
證明透視
錯誤預算與斷言數目從何而來
確定性只在起點使用一次:它使 等於零或一,而不是一個可能在域中相互抵消的路徑數目。唯一不顯而易見的一步是直線歸約。每次平方產生兩個斷言: 關於 , 關於 ;若分別檢查,第 層會剩下 個斷言,於是第零層有 個斷言,驗證者便需要指數時間。把它們合併到一條直線上,每層恰好只剩一個斷言。錯誤預算是逐項相加的:求和檢驗至多 ( 輪、次數為二),隨機直線至多 ,所以每層為 ;只要 , 層合共為 。論證在第零層完成:若斷言在該處仍然為假,便會與直接計算出的 值比較而被拒絕。若域小得多,例如 ,上界便會超過 ,甚麼也不能保證。
常見錯誤
(為何論證使用確定性組態圖)
矩陣項在所選的域中計算路徑數目。對於非確定性圖,接受路徑的數目可能被特徵數整除,因而在域中等於零,即使接受路徑存在。例如,若起始組態有兩個後繼,且兩者在下一步都移向接受匯點,則從起始到匯點有兩條長度為二的路徑,而在特徵數為二的域中 。確定性的空間有界判定機從起始組態出發只有唯一的計算;吸收匯點使有關的項恰好為零或一,避免了這個抵消問題。
IP 的多項式空間上界已於量化公式配套單元中獨立證明,方法是枚舉公開對話記錄並計算與之相容的私有隨機帶。結合兩個包含關係,得 。本處的證明使用局部組態矩陣構造與求和檢驗;它並不依賴另一條由 TQBF 到 IP 的算術化路線。
練習與解答
快速檢查
(為何對於編碼後的確定性計算, 的起始行恰有一個非零項?)
從起始組態出發跟隨計算 步。
解答 · 答案
每個可達的組態只有一個後繼。對步數作歸納,得出從起始組態出發恰有一條路徑,其矩陣項為一;吸收匯點在停機後保持唯一性。
快速檢查
(為何基底多項式必須是多重線性延拓,而不能只是任何在布爾點上取值相同的多項式?)
隨機直線這一步依賴哪一個次數界?
解答 · 答案
隨機直線的限制必須有已知的次數界,至多為 。任意一個取值相同的多項式可能含有在布爾方體上為零的高次項,使根的數目上界失效。
快速檢查
(平方被加項對每個 的個別次數界是多少?)
數一數 出現在多少個因子之中。
解答 · 答案
至多為二: 出現在兩個因子中,而每個因子對該變量都是多重線性的。
快速檢查
(為何驗證者不分別遞歸檢查 與 ?)
經過 層之後會有多少個斷言?
解答 · 答案
分別遞歸檢查會在每個平方層使斷言數目加倍。隨機直線檢驗把兩個端點斷言歸約為一個需要遞歸檢查的斷言。
快速檢查
(若其中一個端點斷言為假,為何證明者所發送的直線多項式不同於真正的直線限制?)
在假端點處比較兩個多項式。
解答 · 答案
所發送的多項式通過兩個端點檢驗,所以在任何被虛假聲稱的端點處都與真正的限制不同。在一點上不同,就表示兩個形式多項式並不相同。
快速檢查
(當 時,對於虛假的初始斷言,經過 層之後得到的上界是多少?)
把各層的誤差相加,並使用聯集界。
解答 · 答案
聯集界給出至多 。