動機
先前的歸約都從一個已知困難的問題出發。只有當某一個問題與 NP 中的每一個語言都建立了聯繫之後,這種做法才有意義。現在我們來構造這種聯繫。給定一個固定的高效驗證者和一個具體的輸入,我們構造一個電路,它剩餘的輸入位就是所提議的證書。當且僅當存在某個證書能使驗證者接受時,該電路可以輸出一。
這一構造不能只停留在「電腦由邏輯閘構成」的說法上。電路的描述必須具有多項式長度,必須有算法能在多項式時間內生成它,並且對其輸入線的每一種賦值都必須有明確的含義。我們將仔細交代帶子視窗、時鐘、短證書與已停機計算。這些細節說明了為甚麼可以表示整個計算,而無需列出指數多個可能的證書。
本單元證明電路可滿足性是 NP 完全的。配套的「閘約束」單元把電路轉化為一個小的布爾(Boolean)公式,並完成關於 SAT 與 3-SAT 的結論。
定義
定義 2.2.1
(布爾電路與 CIRCUIT-SAT)
布爾電路是一個有限有向無環圖,其中明確列出輸入頂點、常量閘、二元 AND/OR 閘和一元 NOT 閘,並指定一條輸出線。一個閘可以為多個後續閘提供輸入。編碼中列出各閘的類型和來源下標,因此輸入變量的個數至多等於描述的長度。格式不合法的描述不屬於 CIRCUIT-SAT。藉助拓撲排序,可以在多項式時間內對給定賦值求值。CIRCUIT-SAT 問的是:是否存在某個賦值使指定輸出為一。
定義 2.2.2
(規範化的證書格式)
固定一個語言 、一個確定性驗證者 以及證書長度的顯式多項式界 。我們可以使用證書長度僅依賴於 的固定長度驗證者。令
長度為 的證書由一個 位整數 和隨後的 個載荷位組成。若 則拒絕;否則把前 個載荷位交給 ,其餘忽略。原來的每個短證書都可以表示出來,而新證書被接受時就給出一個被接受的原證書。當 時,標頭和載荷都為空,它們表示唯一的空證書。
把規範化後的驗證者記為 。採用確定性單帶機,具有固定的有限字母表、雙向無限的帶子,讀寫頭可向左、向右移動或保持不動。其初始帶內容為 ,其中 是分隔符, 恰有 位。這是我們證明中使用的驗證者模型;標準機器模型之間的多項式模擬是其通常的機器無關詮釋的背景知識。固定一個已知的多項式時鐘 ,它界定 在這類輸入上的每一次計算(包括格式錯誤的證書標頭),並將其放大使得 ,其中 是初始非空白串的長度。
令接受狀態與拒絕狀態為吸收態:它們保持相同的狀態、被掃描符號和讀寫頭位置。於是恰好運行 步與提前停機給出相同的答案。可滿足賦值不容許選擇時鐘或機器。
定理/命題
定理 2.2.3
(有界驗證者具有多項式規模的電路)
對於上述固定的規範化驗證者和時鐘,可以由 構造一個具有 個輸入變量的電路 ,使得
該電路有 個閘,並且可以在多項式時間內構造。其中隱含的常數依賴於所固定的機器,而不依賴於 或 。
定理 2.2.4
(電路可滿足性是 NP 完全的)
CIRCUIT-SAT 屬於 NP,並且 NP 中的每個語言都有到它的確定性多項式時間多一歸約。該歸約把 映到電路 ,而不是映到某個被猜出的接受計算。
證明思路
有限視窗就足夠
證明
(為何有限視窗已經足夠)
記 ,。在時刻 ,讀寫頭與其起始位置零的距離至多為 。我們表示從 到 (含兩端)的帶子位置。這個視窗有 個單元,包含整個初始串,並在兩側留有空白緩衝。在被模擬的 步移動中,讀寫頭永遠不會到達端點。把端點之外的鄰居視為空白;這一約定不會影響這裏所表示的真實計算。
令 為帶字母表, 為狀態集。單元標記要麼是普通符號 ,要麼是帶標記的符號 ,表示讀寫頭在該單元上且處於狀態 。合法組態恰有一個帶標記的單元。標記字母表 是固定有限的。用固定的單射把每個標記編碼為 位。沒有分配給標記的編碼將以任意預設輸出處理,使每個電路閘計算的都是全函數。
為甚麼三格鄰域決定下一個單元
證明
(三格規則是一個固定電路)
對於合法組態,位置 的下一個標記只依賴於位置 。若讀寫頭在 ,其轉移寫入一個符號,並保留或去掉那裏的標記。若讀寫頭在 且向右移動,它的新狀態標記 處已有的符號。讀寫頭在 向左移動時情形類似。若沒有讀寫頭進入且中心單元未被標記,則其符號保持不變。更遠的讀寫頭一步之內無法到達 。
因此存在一個固定函數 ,它在合法組態中出現的每個鄰域上與機器一致。其餘的三元組可給定任意固定輸出,例如空白標記。我們並不聲稱任意一組帶標記的單元都描述一個計算;進入模擬的只有合法的初始組態。
的每個輸出位都是 位的布爾函數。它可用真值表構造:對每個使其輸出為一的輸入模式,構成刻畫該模式的合取式,再取這些合取式的析取。把任何寬的合取/析取替換為二元閘。至多有 個模式,由於 固定,這是一個常數。因此更新一個單元只需常數個閘。更新整個視窗需要 個閘。
概念視角組合
把計算看成由單元標籤組成的表
把各層寫成一個有 行、 列的表:第 行列出 步之後的各單元標籤。三格規則說明,表項 就是 作用於表項 。因此, 接受 ,恰好當以初始紙帶開頭、逐行套用這條規則的表,其最後一行含有接受標籤。
搭建各層並讀出接受
證明
(分層、歸納與接受)
初始層包含 、分隔符、空白以及初始讀寫頭/狀態的常量。每個載荷位或標頭位都是電路輸入。其帶符號編碼的某個固定位,取決於符號零與一所選的編碼,它或者是常量,或者是該輸入位,或者是其否定。因此這一層可以顯式構造,需要 個閘;賦值不能再任意選擇多位字母表。
把視窗更新電路複製 份並依次組合,把每一層連到下一層。我們對 作歸納:對證書線的每一種賦值,第 層都編碼 在 步之後的組態。第 層按構造就是初始組態。若第 層編碼真實組態,則每個單元的鄰域都是合法的,固定函數 給出真實的下一個標記,所以第 層編碼 步之後的組態。因此最後一層就是真實的時刻 的組態。在每個單元處檢驗其標記是否帶有接受狀態,並對這些檢驗取或。恰有一個讀寫頭,所以輸出為一當且僅當接受。吸收的停機狀態保證提前的接受在最後一層仍然可見。
閘的總數為 。為輸出描述,遍歷層號與單元號,寫出固定的局部閘模式,其來源下標指向前一層。機器的轉移表和局部真值表的規模是常數。下標只需要 位,所以整個描述具有多項式長度並可在多項式時間內生成。構造過程中沒有求解任何實例,也沒有猜測任何證書。
證明透視
歸納的兩個部分各用到甚麼
歸納有基始步和遞推步,兩者用到不同的假設。基始步只通過 的各位使用自由線:無論賦值如何,初始層都恰有一個帶標記的單元和一個格式正確的帶內容,所以時刻 的合法性是自動成立的。遞推步在合法鄰域上使用三格規則,固定的機器和有界的視窗在這裏起作用:讀寫頭永遠不會到達端點,而且 的規模是常數。歸納避免了任何關於任意位陣列的斷言。我們從不聲稱滿足若干局部條件的某一層就是整體合法的;合法性是從初始層繼承而來的。只看最後一層就足以判斷接受,是因為停機狀態是吸收的;規模界則是 層乘以 個單元,每個單元的代價是常數。
接下來由這個構造讀出 NP 完全性的兩個部分。
成員資格與困難性
證明
(成員資格與困難性)
最後,CIRCUIT-SAT 屬於 NP:證書給出其顯式列出的輸入位的賦值,求值即驗證輸出。關於困難性,固定任意 及其驗證者。該構造給出
這就是所要求的成員資格等價。規範化與電路構造都是多項式的,所以歸約是多項式的。不同的語言可以使用不同的固定驗證者和時鐘;完全性並不要求對所有語言存在一個通用的常數大小的電路。
例題詳解
例題 2.2.5
(在不改變問題的前提下表示較短的證書)
設原證書長度界為 。則 ,規範化後的長度為八。要表示原證書 ,取標頭 ,後接載荷 。規範化驗證者讀到長度二,只把 交給原驗證者。把最後三個載荷位換掉不會改變任何結果。標頭 編碼六,無論其載荷如何都必須被拒絕。填充並不意味著任意的尾隨位是原證書的一部分。
例題 2.2.6
(讀寫頭進入鄰居的單元)
設某個轉移為 。中心被標記為 的鄰域失去該標記,並得到普通符號零。緊鄰其右側的單元,若此前含有普通符號 ,則變為 。它的帶符號並沒有被零覆蓋:零是寫在原來讀寫頭所在位置的。例如,相鄰標記 變為 。三格規則所記錄的正是這一細微區別。
例題 2.2.7
(時鐘估計就是規模估計)
取一個玩具輸入視窗長度 ,時鐘 。所選位置從 到 ,共得到 個單元塊。二十個更新層需要 次局部塊更新。若一次塊更新使用固定的 個閘,則這一部分電路至多使用 個閘。這並不是對可能的帶子或證書的計數;它統計的是一次可重複使用的模擬中的顯式操作。讓 以二次方增長,規模界隨之增長,而依賴於機器的 保持不變。
常見錯誤
常見錯誤
(把常數當成自由參數)
字母表和狀態集之所以是常數,只是因為驗證者在歸約開始之前就已固定。如果機器的描述本身是可變輸入的一部分,把它全部藏進常數的規模估計就是無效的。
常見錯誤
(由機器描述推斷時鐘)
同樣,時鐘是一個指定的多項式界,由證明該驗證者在多項式時間內運行的論證所提供。我們並不是聲稱存在一個能從任意機器描述推斷出運行時間界的算法。
下面的斷言聽起來無傷大雅,但在一部具體的機器上會失敗。
反例模式
取消吸收約定
斷言:更新函數 只需遵循轉移表,所以停機狀態不需要規則。取一個一步之後進入接受狀態 的驗證者,時鐘 。在時刻 ,帶標記的單元是 。轉移表中沒有這個標記的條目,於是 返回預設的空白標記,標記就消失了。在時刻 沒有任何單元帶接受狀態,最後的檢驗輸出 ,電路便拒絕了 本來接受的輸入。斷言不成立。修正:令接受與拒絕狀態為吸收態,使 把 映到自身;於是接受標記在時刻 仍然存在,最後的檢驗輸出 。
常見錯誤
(把電路誤當成公式)
這個電路還不是普通的公式。一個閘可以向多個後繼提供輸入,每次都複製它的全部計算可能導致指數級增長。下一單元引入輔助變量,在產生公式的同時保持這種共享。僅僅因為模擬有多項式個閘,並不能為把其輸出樸素地展開成多項式大小的公式提供依據。
總結
規範化證書長度,固定多項式時鐘,編碼合法的初始帶,再分層模擬局部更新。帶子視窗與局部字母表給出多項式的閘數,顯式下標則給出多項式時間的構造器。自由的輸入線表示證書,因此電路可滿足性恰好刻畫了高效的存在性驗證。
練習
快速檢查
(原證書長度界為七時,求標頭長度與規範化證書總長度。空證書如何表示?)
先計算 。
解答 · 答案
標頭長度為 ,總長度為十。標頭 指明空的原證書;七個載荷位被忽略。每個三位標頭現在都描述從零到七的一個容許長度。
快速檢查
(為甚麼無效的單元編碼可以獲得任意的更新值而不破壞歸約?)
想想哪些組態真的會出現。
解答 · 答案
每個證書賦值都產生有效的初始標記。歸納法表明此後每個標記都是機器的真實標記,因為局部函數在合法組態上與轉移規則一致。那些任意取值的情形永遠不會出現。如果我們轉而容許任意的初始組態,這一論證就不再適用。
快速檢查
(設初始串長度為 ,時鐘為 。共表示多少個單元,使用多少次局部更新?)
使用 。
解答 · 答案
共有 個單元,十五層給出 次局部更新。完整的閘數統計中仍須計入每次更新的常數閘代價以及最後的接受檢驗。
快速檢查
(說明為甚麼找到一個使 輸出零的賦值並不能證明 。)
比較成員資格中的量詞。
解答 · 答案
該賦值只表明某一個所提議的證書失敗。成員資格問的是是否存在某個賦值被接受。要證明不屬於,就必須證明每個可能的賦值都失敗;歸約並不把這個全稱命題歸約為一次失敗的嘗試。
Trevisan–Williams 的電路證明提供了一個可以互補參照的材料。這裏明確規定了有限的帶子緩衝和證書長度約定,使該歸約可以當作一個算法來理解。