某些算法問題中,檢查給定的解似乎比找出解容易。給定頂點列表,檢查每對頂點是否相鄰並不困難;要找出大的相鄰頂點集合,卻可能需要檢查過程無須作的選擇。複雜度理論精確描述這個差別;歸約讓我們保留問題之間的邏輯關係,傳遞求解方法與困難性。
動機
若有適用於任意圖的快速大團算法,可把另一搜尋問題高效地翻譯成圖,使原解對應於團。圖算法便能經這個翻譯求解原問題。翻譯稱為歸約,方向決定算法可傳遞的對象。
我們先把問題寫成是非判定。CLIQUE 詢問圖是否含有大小至少為指定值的團;歸約只需保留這個真值。最優化與搜尋問題還需額外論證:判定答案不會自動給出實際的團。
構造從短子句的合取公式開始。每個子句至少要有一個真文字。我們為每次文字出現建立頂點,並連接來自不同子句且相容的選擇。觸及每個子句的團,便表示一組全局一致的滿足選擇。必須證明雙向對應;只從滿足賦值建團,還不能排除不可滿足公式產生團的錯誤肯定結果。
定義
語言 是答案為「是」的有限二進制字串集合,用來表示判定問題。固定圖、公式與整數的編碼,拒絕格式錯誤者。輸入規模 指編碼長度,而非所含最大數。在標準離散位元模型上,類 由可用確定性算法在關於 的多項式時間內判定的語言構成。
若存在確定性驗證器 和多項式界 ,使得
則稱語言屬於 ,其中對於長度不超過該界的見證,驗證所需時間是關於 的多項式。字串 稱為證書或見證。這個等價式要求每個是實例都有見證,並且禁止任何接受性見證對應於否實例。如果檢驗一個見證需要指數時間,那麼僅有短見證是不足夠的。如果容許見證任意長,而只要求關於該見證的多項式時間,也不符合上述類的定義。
多項式時間多一歸約 是一個可在多項式時間內計算的全函數 ,使得對每個輸入字串 ,都有 當且僅當 。它翻譯輸入,並保持其是或否的答案。若 NP 中的每個語言都可歸約到語言 ,則稱 是 NP 困難的。若 既是 NP 困難的又屬於 NP,則稱它是 NP 完全的。僅有難度並不能確立屬於 NP。
在有限簡單無向圖 中,團是這樣的頂點子集:其中任意兩個不同頂點之間都有邊。獨立集是其任意兩個不同成員之間都沒有邊的頂點子集。頂點覆蓋是與每條邊都相交的頂點子集。CLIQUE 和 INDEPENDENT SET 詢問是否存在相應類型、大小至少為 的集合;VERTEX COVER 則詢問是否存在大小至多為界 的集合。我們使用非負整數閾值,平凡的越界情形可以直接判定。
圖以顯式頂點及邊列表,或鄰接矩陣編碼;孤立頂點也佔用空間。因此頂點數由輸入長度的多項式界定。只用二進制頂點數隱式表示指數多個孤立頂點,屬於另一輸入模型,不適用於下文歸約。
布爾(Boole)文字是一個變量或其否定。子句是若干文字的析取,合取範式(CNF)是若干子句的合取。這裏的 3SAT 指子句至多含三個文字的 CNF 公式的可滿足性。子句可以只含一個或兩個文字;如果希望採用另一種慣例,可以透過重複某個文字把它們補足為恰好三個。含有空子句的公式不可滿足,而不含任何子句的合取則為真。
定理/命題
定理 13.1.1
(歸約傳遞算法並且可以複合)
若 且 ,則 。多項式時間多一歸約是傳遞的。因此,若 是 NP 困難的且 ,則 是 NP 困難的。若此外 ,則 是 NP 完全的。
定理 13.1.2
(三個等價的圖證書)
設 有 個頂點, 為它的簡單補圖:其中兩個不同頂點相鄰,當且僅當它們在 中不相鄰。對於 ,
這些等價關係給出多項式時間歸約,並且這三個判定問題都屬於 NP。
定理 13.1.3
(選取相容的文字產生團歸約)
給定一個含有 個非空子句的 3CNF 公式,為每個文字出現建立一個頂點。當且僅當兩個頂點屬於不同的子句,並且它們的文字不是某個變量與其否定時,在它們之間連邊。該公式可滿足,當且僅當所得的圖含有大小至少為 的團。該構造至多有 個頂點,其編碼長度和構造時間都是多項式的。
證明思路或證明
證明
(歸約可複合並傳遞算法)
要借助 的判定器來判定 ,先計算 ,再在其上運行該判定器。多項式時間的翻譯至多只能輸出多項式個位元,因此 是關於 的多項式。於是,關於 的多項式運行時間,仍然是關於 的多項式。兩個翻譯的複合保持答案的等價性以及同樣的長度界,由此證明傳遞性。NP 難度的蘊含由以下複合得到:把 NP 中任一語言歸約到 的歸約,與給定的從 到 的歸約相複合。
證明
(三個圖等價關係及其驗證器)
對於圖的等價關係,子集內的每一對不同頂點在 中都由邊連接,當且僅當其中每一對頂點在補圖中都是非邊。此外,對任意圖 ,集合 是獨立集,當且僅當 是頂點覆蓋。事實上,未被覆蓋的邊的兩個端點都在 中,而這樣的邊恰恰就是獨立性的失敗。對頂點子集取補集,把大小 變成 ,從而把下界閾值 變成上界閾值 。在鄰接矩陣表示下,構造圖的補圖需要 次頂點對檢查。
要驗證團,檢查給定的列表是否含有至少 個互不相同的合法頂點,並檢查每一對頂點。獨立集的驗證器檢查這些頂點對之間沒有邊;頂點覆蓋的驗證器掃描所有邊,檢查每條邊都有一個端點在列表中,並檢查列表大小至多為給定的界。頂點列表的長度是多項式的,每項檢查也是多項式的。屬於 NP 的證明獨立於難度的證明。
證明
(子句到團的歸約)
現在取公式的一個滿足賦值。在每個子句中選取一個為真的文字出現。所選頂點屬於不同的子句,並且沒有兩個所選文字互補,因為一個賦值不可能使兩者同時為真。所以所有頂點對都是邊,這 個頂點構成一個團。
反之,團中沒有兩個頂點來自同一子句,因為該構造在子句內部不放置任何邊。團至多有 個頂點。因此,大小至少為 的團恰好在每個子句中含有一個文字出現。所選的出現中沒有互補的文字。把每個被選中的正變量設為真,把每個被選中的負變量設為假;兩兩一致性保證這些指令是相容的,即使同一個變量被多次選中也是如此。對從未被選中的變量任意賦值。每個子句都有一個被選中的真文字,因此整個公式被滿足。
文字出現至多有 個,所以檢查每一對是多項式的。文字的變量名同樣佔用位元;構造時間包括比較這些名字,並且仍是關於整個公式編碼長度的多項式。含有空子句的公式可以直接映射到一個固定的否 CLIQUE 實例,空合取則映射到一個固定的是實例。格式錯誤的源字串同樣映射到一個固定的否實例。這使歸約成為全函數,而不會留下未定義的特殊編碼。
證明透視
缺失的邊與存在的邊各有其作用
省略子句內部的邊,迫使大團觸及互不相同的子句。省略互補文字之間的邊,使所選的指令保持一致。閾值則迫使每個子句都有代表。這是三項相互獨立的義務;只滿足其中兩項的圖編碼,可能接受本應被拒絕的公式。
證明
(以至多三個文字的子句取代 SAT)
為完整起見,說明為甚麼可以用 3SAT 代替 SAT。用二元 AND、OR 閘和一元 NOT 閘表示一個布爾公式,並為每個內部閘的值引入一個新變量。對於 AND 閘 ,施加子句 、 和 。對於 OR 閘,使用 、 和 。對於 NOT 閘 ,使用 和 。最後用一個單位子句斷言輸出變量為真。
各組子句恰好強制對應的閘真值表。原滿足賦值按實際閘值擴展後滿足全部子句;反之,子句的滿足賦值沿閘序必須符合每個閘並令輸出為真。新增變量與子句數對公式樹大小為線性,故轉換在多項式時間內保留可滿足性,且各子句至多三個文字。結合所引 Cook–Levin 定理,3SAT 是 NP 完全的;圖歸約再把困難性傳至 CLIQUE、INDEPENDENT SET 和 VERTEX COVER。
例題詳解
例題 13.1.4
(從相容的選擇中讀出賦值)
取 。它的三個子句組含有六個文字出現頂點。在第一個子句中選 ,在第二個中選 ,在第三個中選 。它們兩兩不互補,因而構成一個三元團。它們的指令給出 為真、 為真、 為假,滿足每個子句。若在前兩個子句中選取 和 ,則無論第三個如何選擇都會失敗,因為對應的頂點之間沒有邊。
例題 13.1.5
(對子集取補時閾值會改變)
設 是有四個頂點、邊為 的路。集合 是獨立集,其補集 是頂點覆蓋。在 中,頂點對 是一個團。因此,CLIQUE 實例 映射到獨立集實例 ,再映射到頂點覆蓋實例 。圖的補改變鄰接關係;子集的補改變大小閾值。它們是不同的運算,儘管這個例子同時用到了兩者。
例題 13.1.6
(為甚麼數值參數可能誤導對運行時間的論斷)
對於非負整數元素和目標值 的 SUBSET SUM,通常的動態規劃記錄從零到 的哪些和可以取到,可以使用 次表更新。若 ,則其二進制編碼只需 位,而表卻有 項。該算法關於數值 是多項式的,但並不因此就關於二進制輸入長度是多項式的。這樣的界稱為偽多項式的。這一觀察解釋的是代價模型,並不是 SUBSET SUM 的 NP 難度的證明。
常見錯誤
反例模式
子句內部的邊會接受不可滿足的公式
一個誘人的變體是把同一子句內的頂點也連起來,理由是多加邊只會令大團更容易找到。把它用在不可滿足的公式 ()上:第一個子句中 的兩個出現便相鄰,構成大小為 的團,但沒有任何賦值滿足該公式。原構造不在子句內部連邊,正是為了令大小為 的團必須恰好使用每個子句一次。
常見錯誤
(歸約方向弄反)
要證明新問題 是困難的,應當把一個已知的困難問題歸約到 。從 到已知困難問題 的歸約 ,只在 可解時才提供解 的方法。容易的語言也可以歸約到許多困難的語言。箭咀本身表達的是一種算法上的蘊含,而不是對稱的比較。
常見錯誤
(誤解 NP 這個名稱)
NP 不表示「非多項式」。P 中的問題皆在 NP:驗證器忽略空證書並運行判定器即可。因此 NP 完全性並未證明多項式算法不存在。若某個 NP 完全語言在 P,歸約定理便會使所有 NP 語言屬於 P;是否如此,正是 P 對 NP 問題。NP 的「非確定性」也不同於隨機化:這裏驗證器是確定性的,由存在的見證提供成功的選擇;隨機抽樣找不到見證,並不能證明它不存在。
常見錯誤
(在歸約內部先解決源問題)
歸約應當在不先解決源問題的前提下變換輸入數據。「若公式可滿足則輸出一個是圖,否則輸出一個否圖」在數學描述上保持了答案,但並沒有建立任何多項式時間的構造。相容出現的構造之所以成功,是因為它直接由局部語法構建圖。
總結
NP 描述多項式長度、可高效驗證的證書。多一歸約須在多項式時間內翻譯每個輸入,同時保留是與否的答案。子句文字出現把滿足選擇編碼為團;圖補及子集補再連到獨立集與頂點覆蓋。NP 成員資格、困難性與引用的基礎定理,各有獨立的證明義務。
練習
快速檢查
(說明哪個歸約方向能讓 VERTEX COVER 的多項式時間算法解決 3SAT,並指出兩次圖歸約之後的閾值。)
解答 · 答案
使用 。對於有 個非空子句的公式,其出現圖 有 個頂點,團閾值為 。在補圖中,獨立集閾值為 ,最終的頂點覆蓋閾值為 。空子句和空合取這兩種例外輸入,按構造中所述被直接判定並映射到固定的實例。
快速檢查
(在子句到團的構造中,假設在不同子句裏帶互補文字的兩個頂點之間也加上邊。給出一個不可滿足的公式,使其產生錯誤的肯定結果。)
解答 · 答案
公式 不可滿足,且 。加上多餘的邊後,第一個子句中的頂點 與第二個子句中的頂點 構成大小為 的團,圖因而被錯誤地接受。缺少互補文字之間的邊,才使所選的文字互相一致。
快速檢查
(給出判定問題「這個非空有限無向圖是否有一條恰好經過每個頂點一次的簡單路徑?」的多項式證書和驗證器。)
解答 · 答案
給出所有頂點的一個有序列表。檢查其長度等於頂點數,每個合法頂點恰好出現一次,並且列表中每一對前後相接的頂點之間都有邊。在標準的頂點標號編碼下,該列表有 位,檢查需要多項式時間。單頂點圖有一條僅包含該頂點的路徑。這建立了屬於 NP;並不建立該路徑問題的 NP 難度。
快速檢查
(為甚麼 NP 完全問題的某個固定的容易實例並不與 NP 難度矛盾?請區分實例與語言。)
解答 · 答案
NP 困難性針對整個任意編碼輸入族及其多項式算法。固定圖的答案可存為常數,某些特殊圖類也可有快速算法;兩者都未提供判定所有無限制實例的算法。
練習 13.1.7
(證明:若 且 ,則 。)
核心證明
解答(3)
- 1
為 建立驗證器
對輸入 與見證 ,先用該歸約計算 ,再在 上運行 的驗證器 。
- 2
界定見證長度與運行時間
關鍵一步
歸約是多項式時間的,所以 受 的某個多項式所限。把它代入 的見證長度界與驗證時間,便得到關於 的多項式;再加上計算 的時間,總時間仍是多項式。
依據: 輸出長度的界是多項式時間歸約本身所提供的。
- 3
得出屬於 NP
∎當且僅當 ,當且僅當 在 上接受某個短見證。因此新的驗證器恰好對 的成員接受某個見證,即 。