動機
多項式大小的電路族可以為每一個輸入長度各自包含一個電路,而不要求存在有效率的方法去產生整個電路族。即使如此,若假設每一個 NP 語言都有小電路算法,仍會帶來深遠的後果。具體而言,這會使得一個多項式大小的電路,能夠為某一固定長度的所有相關輸入尋找見證。在全稱挑戰之前先猜出這樣的電路,便可把一個「全稱—存在」兩塊量詞的敘述轉化為「存在—全稱」的敘述。
我們以標準的非一致形式證明 Karp–Lipton 蘊含關係:若 ,則多項式層級等於其第二個存在層級 。此假設目前並不知道是否成立,結論亦屬有條件的。證明並沒有斷言 ,因為非一致的電路族未必可由輸入長度計算出來。
我們採用多項式層級的量詞定義:具體而言, 中的語言具有一個多項式時間謂詞 及多項式有界的定長字串,使得
通常的填充(padding)慣例使每個量詞塊內的所有字串都可具有指定的長度。我們亦以確定性多項式時間計算可由多項式大小電路模擬這一標準結果作為背景知識。見證搜尋的構造及塌縮論證則在下文中予以證明。
判定電路可引導見證搜尋
定義 8.3.1
(見證前綴語言)
設 為多項式時間謂詞,其見證 具有固定的多項式長度 。 的前綴語言為
的驗證者猜出 其餘的位元,檢查 是否為前綴,並計算 。因此 。在 的假設下,它具有多項式大小的判定電路,儘管這些電路未必能一致地構造出來。
定理 8.3.2
(非一致見證搜尋)
假設 。對於每一個具有固定多項式見證長度上界的多項式時間謂詞 ,存在一個多項式大小的電路族 ,使得每當某個長度為 的輸入 具有有效見證時, 便輸出一個有效見證。當不存在見證時,輸出可以是任意值。
證明
(證明)
對於輸入長度 ,從空前綴開始。在 個位置的每一個,詢問對於同一個輸入 ,當前前綴後接零是否屬於 。若是,則附加零;否則附加一。若當前前綴有有效見證,則兩個延伸之中必有一個具有有效見證,因此這個選擇保持該不變式。經過 次選擇後,前綴便是一個完整的有效見證。對於沒有見證的輸入,則無須作出任何正確性斷言。
每個查詢 的長度以 的某個多項式為界。在固定編碼下,這 個階段所涉及的查詢長度由 及階段決定。選取 相應的多項式大小非一致電路,並按需要複製。將編碼硬接線(hardwire),並把每個判定電路的輸出接入下一階段的前綴。展開這多項式個階段,便得到一個多項式大小的電路:多項式個多項式大小的電路副本,加上多項式時間的編碼電路,其總大小為多項式。此電路把每個長度為 的輸入 映射到一個長度為 的字串。我們並不假設存在由 產生此電路族的算法。
例題 8.3.3
(沿著滿足賦值的前綴逐步搜尋)
對於公式 ,空前綴有延伸。詢問前綴 是否有延伸:有,即 。於是將第一個位元固定為零。接著詢問 是否為可通往滿足賦值的延伸:否,故將第二個位元設為一。搜尋返回 。這兩個決定依賴同一條公式,而第二個查詢則依賴第一個答案。展開的過程以電路的連線記錄這種依賴關係;在所構造的搜尋電路中,並沒有枚舉所有賦值。
概念視角組合
把搜尋看成二叉樹上的下降
把所有長度至多為 的前綴排成一棵完全二叉樹。當 ,即 之下存在見證時,標記前綴 。搜尋從根出發(根被標記,當且僅當存在見證),在每個節點處,若以零結尾的子節點被標記就走向它,否則走向以一結尾的子節點。因此它沿著一條被標記的路徑走到葉子,每一步需要向 作一次成員查詢。
常見錯誤
(電路族並不是一致的搜尋算法)
證明是從非一致電路族中,為每個相關長度選取判定電路。它並沒有提供一部多項式時間機器,使其在給定長度後寫出這些電路。對於沒有見證的輸入,搜尋電路可以輸出任意字串;其後的驗證者仍須檢查所提出的見證。這些限定條件,對假設本身以及下文的可靠性論證,都是不可或缺的。
反例模式
多項式大小電路並不給出判定算法
聲稱:有多項式大小電路的語言必可判定,所以 不大於 。取 。對每個 ,電路先檢查 個輸入位元是否全為 ,再輸出一個固定常數,即第 部機器真正的停機答案。它的大小為 ,所以 。若 可判定,停機問題也會可判定。因此 含有不可判定的語言。修正辦法是要求一致性,即有多項式時間算法能由 產生電路,而本定理並不假設這一點。
為何 SAT 已足以作為電路假設
此假設常常只用 SAT 來陳述。這個等價形式依賴於 SAT 通常的 NP 完全性,以及多項式大小電路對多項式時間歸約的模擬;我們將這些標準結果用作背景知識,並說明如何處理輸出長度。
命題 8.3.4
(SAT 的電路已足以涵蓋 NP 的電路)
若 SAT 具有多項式大小的非一致電路,則 。反過來,後者的包含關係蘊含 SAT 具有多項式大小的電路。
證明
(證明)
對於 ,選取一個由 到 SAT 的多項式時間多對一歸約 。對於長度為 的輸入,它產生長度至多為某個多項式 的編碼。一個多項式大小的電路模擬 ,同時輸出填充後的編碼及其實際長度 。對於每一個可能的 ,選取處理長度為 的輸入的 SAT 電路。將輸出的首 個位元輸入該電路,並利用所計算的長度選取其答案。格式不正確的編碼按照固定的 SAT 編碼予以拒絕。可能的 只有多項式個,而每個被選取的電路均具有多項式大小,因此合併後的電路對 而言具有多項式大小,並判定 。電路族的選取是非一致的。反方向是顯然的,因為 SAT 屬於 NP。
例題 8.3.5
(為何輸出長度不能被悄悄忽略)
一個歸約可能對某個長度為 的輸入輸出較短的公式,而對另一個同樣長度為 的輸入輸出較長的公式。電路族為每個實際長度各有不同的電路,因此,只選取最大長度所對應的電路,再把任意填充後的編碼輸入其中,是不足夠的。選擇器構造會對每個可能的長度計算正確的電路;它並不假設填充會保持所選編碼的意義。
同樣的有限長度簿記亦出現在見證搜尋定理之中。若每個前綴查詢的長度至多為 ,而判定電路的大小至多為 ,則 個階段至多使用 個判定閘,另加多項式量級的編碼與接線開銷。 與 均為多項式,故所得的界為多項式。該電路容許包含許多副本,但並不包含列出所有可能見證的指數大小的表。
把全稱—存在敘述移至第二個存在層級
定理 8.3.6
(Karp–Lipton 的關鍵包含關係)
若 ,則 。
證明
(證明)
設 由上述展示的謂詞 給出,並固定輸入長度 。利用多項式時間可解碼的定長編碼構成 。見證長度 是 的多項式,並可從編碼中恢復。必要時對長度作填充,並對關係 應用見證搜尋定理。它給出一個多項式大小的電路:對於每一對具有指定長度、且存在某個有效 的 ,該電路輸出其中一個有效的 。
對於固定的輸入 ,將 硬接線到該電路之中。所得的多項式大小電路 以 為輸入,並輸出一個候選的 。其描述長度以 的某個多項式為界,且對所有長度為 的輸入使用同一個多項式界。考慮以下敘述
檢查 的格式是否正確、計算 、檢查輸出長度以及計算 ,所需時間均為 及描述長度的多項式。將描述填充至固定的多項式長度,並拒絕無效的編碼。因此該敘述屬於 。
若 ,則每個 均有見證,而硬接線的見證搜尋電路對所有 同時有效;於是存在量詞所要求的電路描述存在。若 ,則某個 沒有有效見證。對於該 ,任何電路的輸出均不能滿足 ,所以沒有任何被猜出的電路能使全稱檢查通過。因此該敘述恰好定義 。
證明透視
為何猜出電路會交換量詞
陳述 所要求的見證 ,可以任意地、甚至以指數級複雜的方式依賴於 。證明把這種依賴轉化為短得足以被猜出的東西:一個由 算出 的多項式大小電路 。這是唯一不尋常的一步,亦正是 的用處所在:依據非一致見證搜尋定理,只要依賴關係 真的存在,它便總能由一個小電路實現。此後,對 的存在選擇便排在全稱的 之前,得出 。
有兩點使證明嚴謹。電路是在 固定之後才選的,因此可以把 硬接線進去, 只須對這個 適用。而且檢驗 是對每個 進行的,所以錯誤的猜測絕不可能通過:若某個 沒有有效的 ,則無論 為何, 都不滿足 。這就是電路在沒有見證的輸入上可以輸出任意內容,而不損害可靠性的原因。沒有該假設,便沒有理由認為存在這樣簡短的描述,被猜出的對象也就無法以多項式為界。
例題 8.3.7
(被猜出的電路必須達成甚麼)
設有一個玩具謂詞,對每個兩位元的 ,要求一個兩位元的 等於 的逐位元補碼。電路 對全部四個 值都成功,所以一個描述便能通過全稱檢查。若把謂詞修改為 沒有有效的回應,則無論設計者能力多強,每一個被提出的電路都會在該 處失敗。這個有限的例子說明量詞轉換的完備性與可靠性;它並沒有確立 NP 的小電路假設。
被存在地猜出的對象,是一個必須對給定 的每一個 都適用的電路。它並不是在每次全稱挑戰之後才另行選出的存在見證。反過來,該電路無須在與此 無關的配對上正確;將 硬接線是容許的,因為外層的存在選擇是在得知輸入之後才作出的。
塌縮其餘層級
取補集會互換 與 。對關鍵包含關係取補集,得 ,所以兩個第二層級相等。下面給出所需的歸納,以推出每個更高的層級都與它們相等。
定理 8.3.8
(Karp–Lipton 塌縮定理)
若 ,則 。
證明
(證明)
基礎的等式如上所述。假設對某個 有 。一個 敘述由一個外層的存在量詞塊,接著一個 謂詞組成。根據歸納假設,該內層謂詞具有一個以存在量詞塊開始的 描述。將兩個相鄰的存在量詞塊合併為一個多項式長度的量詞塊,便得到一個 描述,因此 。反方向的包含關係可藉添加虛設的量詞塊而得。
取補集得 。歸納法證明了第二層及以上的所有層級都等於第二層。第一層級因嵌套關係而包含於其中,所以所有固定層級的聯集 PH 等於 。
例題 8.3.9
(合併相鄰的存在量詞塊)
形如 的敘述,可藉由把配對 編碼為單一字串 ,寫成 。若原先兩者的長度均為 的多項式,則其合併後的長度亦為多項式。這個基本的合併正是歸納中所用的步驟;將存在量詞塊與全稱量詞塊互換,則是另一種一般而言無效的操作。
常見錯誤
(有條件的塌縮並不是分離)
該定理陳述的是一個蘊含關係。它並沒有確立 為假,因為多項式層級是否嚴格亦屬未知。它也沒有證明 等於 P。小的非一致電路、一致的多項式時間算法,以及層級塌縮,是互相關連但並不相同的命題。
練習與解答
快速檢查
(為何見證前綴語言 屬於 NP?)
說明證書是甚麼。
解答 · 答案
見證提供 其餘的位元。確定性驗證者可在多項式時間內檢查長度、前綴關係及 。
快速檢查
(在搜尋構造中,當已知存在延伸時,為何對以零結尾的前綴作一次查詢,已足以選出下一個位元?)
考慮答案的兩種情況。
解答 · 答案
若零延伸有見證,則選擇零可保持不變式。否則,由於當前前綴至少有一個完整延伸,每個有效延伸必以一開始;選擇一可保持不變式。
快速檢查
(當不存在見證時,搜尋電路可以輸出甚麼?)
回想定理保證了甚麼。
解答 · 答案
任何符合指定輸出長度的字串。只有在存在有效見證時才保證正確,所以驗證者必須檢查其結果。
快速檢查
(在關鍵包含關係中,當某個全稱選擇 沒有有效的 時,為何沒有任何被猜出的電路能夠通過?)
看看在該特定的 處的檢驗。
解答 · 答案
在該特定的 處,每個字串 都使 失敗。電路的輸出正是這些字串之一,所以無論電路描述為何,全稱檢查都會拒絕。
快速檢查
(為何兩個相鄰的存在量詞塊可以合併,而不提高層級?)
把數對當作一個字串。
解答 · 答案
將兩個多項式長度的字串編碼為一個多項式長度的字串,並讓謂詞對其解碼。兩個存在選擇的次序不會引入新的交替。
快速檢查
(Karp–Lipton 蘊含關係是否證明了 ?)
PH 塌縮是否已知為假?
解答 · 答案
不是。它只是說該包含關係會蘊含 PH 塌縮。若沒有獨立證明 PH 不會塌縮到第二層,則該假設並未被排除。