一個被提出的解有時可以比尋找它快得多地被檢驗。複雜度理論透過短證書(certificate)將這種區別形式化,而歸約則把一個判定問題的困難性轉移到另一個判定問題上。這種轉移的方向至關重要:要證明某個目標問題是困難的,就要把已知的困難實例翻譯成目標問題的實例。
本單元發展使上述說法變得精確的三個想法。第一,我們透過驗證者(verifier)定義 NP 與 coNP 這兩個類,並討論證書能做到與不能做到的事。第二,我們定義多項式時間多對一歸約,並證明它們能傳遞有效率的算法,而且可以複合。第三,我們運用這些工具,給出由 3-SAT 到 CLIQUE 的 NP 完全性論證,並檢視幾個看似誘人但無效的論證。在全文中,「多項式時間」均指確定性圖靈(Turing)機(或任何僅帶來多項式額外開銷的等價模型),所有語言均定義在一個固定的有限字母表上,而實例則以合理的方式編碼為字串。
動機:尋找與檢驗
考慮一個大小為 的數獨盤面。給定一個已完成的盤面,我們可以在盤面大小的多項式時間內檢查每一行、每一列與每一個宮。要從部分填好的盤面得出一個完成的盤面,似乎需要探索龐大的可能性空間,而對於這個推廣後的問題,目前並不知道有多項式時間的方法。廉價的檢驗與看似昂貴的搜尋之間的這種不對稱,正是 NP 這個類所要孤立出來的現象。
這個形式化需要謹慎。一個「解」必須足夠短,以便能被多項式時間的機器讀取,否則檢驗根本無法檢視它。一個「檢驗」必須是確定性且有效率的,而且必須是可靠的:任何虛假的證書都不能使它相信一個否定實例是肯定實例。這些要求明確地出現在下面的定義中。
證書與歸約
定義 2.1.1
(NP 與 coNP)
若存在多項式 與確定性多項式時間驗證者 ,使得 恰好當存在某個長度至多為 的字串 滿足 ,則稱語言 屬於 。類 由 中語言的補集所組成。對屬於 coNP 的語言 ,其否定實例有短的 NP 證書,因為 。這並不聲稱其肯定實例有短的 NP 證書。每個屬於 的語言都同時屬於這兩個類; 是否成立仍是未解決的問題。
對於 SAT,輸入是一個布爾(Boolean)公式,見證則是一個真值賦值。對公式求值即可在多項式時間內檢驗該見證。然而,一個失敗的賦值並不能證明公式不可滿足:其他賦值可能成功。這一觀察並不能證明「不可滿足性」沒有短證書;那樣做將解決一個重大的未解問題。
仔細閱讀定義
定義中有兩種量詞模式,應當區分開來。對於 ,必須存在一個短的 使 。對於 ,每一個短的 都必須使 。以符號寫出,
對此取否定得 。因此,補語言由關於短字串的全稱條件來描述。這個條件不是一份存在性的證書。屬於 的語言則對兩種答案都有可有效檢驗的短證書,分別使用它自身和其補語言的 NP 驗證者。
包含關係 成立,是因為 對補集封閉:只需把判定器的接受與拒絕結果對調。 是否成立同樣是未解決的。若某個 NP 完全語言 屬於 coNP,則可推出 。這是歸約的一個簡潔應用:對 ,歸約 同時也是歸約 ,而 ,所以由下文證明的 NP 對多項式時間原像的封閉性得 。因此 ,再取補集即得 。
定義 2.1.2
(多對一歸約與完全性)
多項式時間多對一歸約 是一個多項式時間可計算的函數 ,滿足 當且僅當 。若 中每個語言都以此意義歸約到語言 ,則稱 為 NP 困難。若 既是 NP 困難又屬於 ,則稱它為 NP 完全。
「當且僅當」包含兩個蘊涵,而每個歸約都必須證明兩者。正向蘊涵()稱為歸約的完全性(completeness),反向蘊涵()稱為可靠性(soundness);等價地,即 。忘記其中任何一個方向都會產生無效的論證,下面的反例將會說明。函數 必須是全函數,且在每個字串上(包括並非格式良好的實例的字串)都能在多項式時間內計算;標準的約定是把格式不良的輸入映射到一個固定的、不屬於 的字串,前提是 不是所有字串的集合。
命題 2.1.3
(歸約傳遞有效率的判定程序)
若 且 ,則 。多項式時間多對一歸約具有遞移性。
證明
(把歸約與判定器複合)
對於輸入 ,計算 ,然後執行 的多項式時間判定器。成員資格的等價性使答案正確。 的輸出長度至多等於其運行時間,因此是 的多項式;把兩個多項式界複合起來仍是多項式。遞移性則由複合歸約函數並應用同樣的長度界而得。
這個命題通常以其逆否形式使用:若 且 ,則 。由於目前並不知道有任何 NP 完全語言位於 之外,實際的解讀是有條件的:若 是 NP 困難的且 ,則 是 NP 困難的,而 只有在 時才屬於 。
配套的驗證者電路與門約束兩節證明了 Cook–Levin 構造以及 SAT、3-SAT 的 NP 完全性:先規範短見證,再模擬帶時鐘的驗證者,最後加入保持可滿足性的局部門約束。下面的圖例題使用其中的 3-SAT 結論作為背景。3-CNF 公式是子句的合取,每個子句包含三個文字出現;這裏容許重複文字。配套單元亦給出了變量互異約定所需的構件。
一個完全性證明
對於新語言 ,每個 NP 完全性證明都遵循同一個模板,在給出例子之前值得先陳述這個模板。
- 透過描述一個證書和一個多項式時間驗證者,證明 。
- 選取一個已知為 NP 困難的語言 。
- 定義函數 ,並證明它可在多項式時間內計算。
- 證明 。
- 證明 。
定義 2.1.4
(CLIQUE 與子句出現圖)
CLIQUE 由數對 組成,其中 是有限簡單無向圖,且含有 個兩兩相鄰的頂點所成的集合。給定一個有 個子句的 3-CNF 公式,為每個文字出現建立一個頂點。當來自不同子句的兩個頂點的文字並非互補時,恰好把它們連起來。設 。
定理 2.1.5
(3-SAT 歸約到 CLIQUE)
對有 個子句的 3-CNF 公式 ,令 為其子句出現圖,並設 。則 可滿足當且僅當 有 -團,而且 可在多項式時間內計算。由於 CLIQUE 屬於 NP,CLIQUE 是 NP 完全的。
證明
(團歸約的兩個方向)
一個滿足的賦值從每個子句中選出一個為真的出現。被選出的頂點構成一個 -團:為真的文字之間不可能互相矛盾。反過來,一個 -團在每個子句中至多含一個頂點,因此每個子句恰有一個。它的文字不含互補對;把它們的變量指派為使所有被選出的文字為真,其餘的變量任意指派。每個子句都被滿足。圖與 都可在多項式時間內構造,這就確立了歸約的兩個方向。
CLIQUE 屬於 NP:由 個相異頂點組成的列表是一個證書,並且可以檢查所有頂點對是否有邊。因此,由 NP 完全的 3-SAT 出發的歸約證明了 CLIQUE 是 NP 完全的。由 CLIQUE 到 3-SAT 的歸約會顯示相反方向的轉移,其本身並不能證明 CLIQUE 是困難的。
證明透視
為甚麼團的論證成立
有兩個細節值得明確評論。第一,同一子句中的頂點永不相鄰,因此一個團在每個子句中至多使用一個文字出現。由於目標大小是 ,而子句恰有 個,鴿籠原理迫使每個子句恰有一個頂點。若沒有這個限制,一個大小為 的團可能使用來自同一子句的多個頂點,而完全遺漏另一個子句,這樣它就不能證明每個子句都被滿足。第二,「並非互補」恰好就是一致性條件:一組文字出現可以被同一個賦值同時變為真,當且僅當它不含任何一對 。若同一個文字出現在兩個被選中的子句中,則同一個賦值使兩者皆為真,這就是為甚麼相等的文字要被連起來。
以下互動使用另一個雙子句公式;可把它的文字出現位置選擇與下方三子句例子比較。
例題 2.1.6
(歸約的一個具體實例)
取 ,其中 個子句,並把出現記為:子句 1 中的 ;子句 2 中的 ;以及子句 3 中的 。共有 個頂點。在不同子句之間,邊是除互補對之外的所有頂點對。在子句 1 與 2 之間,互補對為 ()、、、、(),因此有 條邊,即 。在子句 1 與 3 之間,互補對為 ,因此有 條邊。在子句 2 與 3 之間,互補對為 、、,因此有 條邊。該圖有 條邊,且 。
這個公式是可滿足的:取 為真、 為假。子句 1 透過 為真,子句 2 透過 為真,子句 3 透過 為真。三元組 是一個團: 是一條邊(見上面的計算), 並非互補( 對 ),而 連接相等的文字 。反過來,三元組 不是團,因為 是互補對 ;對應地,從子句 1 選 、從子句 2 選 、從子句 3 選 ,會要求 同時為假與為真。歸約在這個實例上的表現與所宣稱的一致。
例題 2.1.7
(不可滿足的公式沒有團)
取 ,則 、,圖有 個頂點。子句 1 的每個文字都是 ,子句 2 的每個文字都是 ,所以全部 個跨子句的頂點對都互補,不畫任何邊。-團至少需要一條邊,所以不存在,與 不可滿足一致。若採用連接互補文字的錯誤規則,九條邊都會出現,見下面的常見錯誤。
無效的論證與反例
由於歸約的方向很容易混淆,具體地看看無效的論證如何失敗是有用的。
常見錯誤
(驗證不等於搜尋)
驗證者必須對每個肯定實例,在至少一個短見證下接受;並對每個否定實例,拒絕每一個見證。它不需要找出見證。能有效率地檢驗一個被提出的解,並不意味著目前已知有有效率的方法去尋找一個解。
常見錯誤
(朝錯誤的方向歸約)
假設有人證明了 ,並因此斷定 CLIQUE 是 NP 困難的。這並不成立。存在一個由 CLIQUE 到 3-SAT 的翻譯,只顯示 CLIQUE 不比 3-SAT 更困難。事實上,每個屬於 的語言都歸約到任何至少包含一個字串且至少遺漏一個字串的語言:若 ,且 、,則當判定器接受 時令 ,否則令 。特別地,每個屬於 的語言都歸約到 SAT,然而這對其困難性沒有任何說明。
常見錯誤
(只證明等價的一個方向)
在團構造的一個有缺陷的變體中,把來自不同子句的所有頂點都連起來,包括互補的頂點。一個滿足的賦值仍然產生一個 -團,但不可滿足的公式 產生六個頂點,且每個跨子句的頂點對都相鄰。由於 ,任何這樣的一對都是 -團。反向蘊涵不成立,所以這不是歸約。
最後這個例子具體地說明了邊的規則中為何要有「並非互補」:它恰好使逆向的方向成立。
若 SAT 屬於 coNP,則 NP 與 coNP 相等。這就是為何一般不相信 SAT 屬於 coNP:那會使兩個被普遍認為不同的類塌縮。這種信念並非定理,而這裏也沒有任何結果證明 。
連同下面的封閉性及遞移性,這蘊涵:若 是 NP 完全的,且 其中 ,則 是 NP 完全的。這正是單一個已確立的困難問題能夠催生整個困難問題族的精確含義。
反例模式
容易的問題也可歸約到 SAT
錯誤說法是,只要 就能推出 是 NP 困難的。取 ,把每個輸入都映到固定的不可滿足公式 。這是多項式時間多對一歸約,因為兩邊的成員關係始終都不成立;實際上,所有字串構成的語言不可能歸約到空語言:肯定實例的像必須屬於空集。要證明目標問題困難,應從已知困難問題出發,歸約到該目標。
本章的圖問題顯式編碼所有頂點, 是以二進制表示的非負整數。驗證者先拒絕大於頂點數的 ,而不會嘗試讀取過長的證明。格式錯誤的編碼不屬於這些語言。
命題 2.1.8
(NP 對多項式時間原像封閉)
若 且 ,則 。把歸約與驗證者複合即可證明;多項式輸出長度界同時控制證書長度。
證明
(把歸約與驗證者複合)
設 為該歸約, 為 的驗證者與界。定義 。由於對某個多項式 有 ,長度至多為 的證書已經足夠,而 在多項式時間內運行,因為計算 與在多項式長度的輸入上執行 都是多項式時間。若 ,則 ,且某個短的 被接受;若 ,則 ,且每個 都被拒絕。所以 。
例題 2.1.9
(很大的數值閾值不需要很長的證明)
一張顯式列出的圖有五個頂點,而二進制閾值表示 。它不可能有這麼大的團。驗證者讀取閾值和頂點數後即可拒絕,無須索取一千個標籤。若 ,候選列表 會因重複而在檢查邊之前被拒絕;對 則檢查三對頂點。證明驗證的是所選集合,並不聲稱不存在更大的團。
練習與解答
快速檢查
(為甚麼 ?)
由證書的定義開始。
解答 · 答案
驗證者可以忽略其證書,並直接執行該語言的多項式時間判定器。對於肯定實例,空證書已經足夠。
快速檢查
(一個歸約把 映射到 。若 有多項式時間判定器,可推出甚麼?而僅僅由 是容易的,又不能推出甚麼?)
先計算,再判定。
解答 · 答案
計算該歸約,然後判定 ;這在多項式時間內判定 。 容易並不蘊涵 容易:歸約可能只到達 的實例中一個容易的子集。
快速檢查
(在證明 NP 對多項式時間原像封閉時,為何長度至多為 的證書已經足夠?)
先界定 的長度。
解答 · 答案
驗證者 作用於 ,而 。取 為非遞減(這不失一般性), 需要的證書長度至多為 。
快速檢查
(在由 3-SAT 到 CLIQUE 的歸約中,公式有 個子句。請說明頂點數目與邊數的最大可能值,並計算 的確切邊數。)
數一數互補對。
解答 · 答案
有 個頂點。在兩個不同子句之間有 個頂點對,而子句對共有 個,因此至多有 條邊,當不存在互補對時達到。對於給定的公式,,所以有 個頂點與 個跨子句的頂點對。互補對有: 一對, 四對(),共五對,所以有 條邊。賦值 為真、 為假滿足該公式,而 的頂點與第一個 的頂點構成一個 -團。