動機
貪心與動態規劃未能解某問題,本身並未證明問題困難。歸約給出更精確比較:若能高效解一個問題,就能高效解另一個。NP 完全性圍繞具有短而易驗證證書的問題,組織這些比較。它描述最壞情況的多項式時間可解性,並非聲稱每個小實例都實際上無法求解。
本篇以二進制字串編碼,按輸入位元計時。圖明確列出頂點及邊,所以編碼長度至少為頂點數。非負整數閾值以二進制表示;負閾值欄位視為格式錯誤。格式錯誤可在解析時拒絕。宣稱構造輸出大小為多項式時,這些約定不可省略。
定義
定義 4.1.1
(判定問題、P 與 NP)
判定問題用所有是實例構成的語言 表示。若確定性算法對每個輸入都在輸入長度的多項式時間內停止並判定成員資格,則 在 P。若存在多項式 及確定性多項式時間驗證器 ,使
則 在 NP。字串 稱為證書。驗證器對其總輸入長度為多項式時間;證書長度界保證合法證書的驗證成本亦為 的多項式。
每個 P 語言都在 NP:驗證器可忽略證書,直接執行判定算法。NP 並非「非多項式」,它包含容易問題;定義既未提供高效找證書的方法,也未要求否實例有短證書。P 是否等於 NP 仍未解決,見 Clay Mathematics Institute。
定義 4.1.2
(多對一歸約與完全性)
多項式時間多對一歸約 是總定義的多項式時間可計算函數 ,對每個輸入均有 當且僅當 。若每個 NP 語言都歸約到 ,稱 NP 困難;若它還屬 NP,則稱 NP 完全。
計算歸約函數時,不能先假定知道 是否為是實例。等價的兩個方向保持是與否答案。把所有來源實例變成容易的是實例並非有效歸約,除非來源本來沒有否實例。可把來源格式錯誤的輸入送到目標的固定否實例,使函數總定義。
定理 / 命題
定理 4.1.3
(傳遞算法與困難性)
若 且 ,則 。歸約具傳遞性。因此,若 NP 完全語言 歸約到 ,且 ,則 NP 完全。若任何 NP 完全語言在 P,則 P=NP。
定理 4.1.4
(具體的 NP 完全圖問題鏈)
假設標準的 3-SAT NP 完全性,則以下判定問題均 NP 完全:CLIQUE,問是否有至少 個兩兩相鄰頂點;INDEPENDENT SET,問是否有至少 個兩兩不相鄰頂點;VERTEX COVER,問是否有至多 個頂點接觸每條邊。
外部依賴。 本篇使用但不證明一般計算到公式定理,以及 3-SAT 的 NP 完全性。Stephen Cook 的官方問題說明第二節 陳述此起點。下面歸約均完整證明,但不能取代未展開的計算表格證明。3-SAT 是每子句恰有三個文字出現位置的合取式,容許重複;文字指變量或其否定。
證明思路或證明
證明
(算法傳遞與傳遞性)
要用 的求解器判定 ,先計算 ,再把輸出交給求解器。歸約為多項式時間,寫出每位元需要時間,所以輸出長度亦為多項式。求解器對輸出長度的多項式成本,遂仍是 的多項式。定義中的等價保證答案正確,證明第一斷言。
傳遞性由複合歸約函數得到。同一輸出長度論證限制第二函數時間,所以複合為多項式且保持等價。若所有 NP 語言歸約到 ,再由 歸約到 ,傳遞性使 NP 困難;屬 NP 再補上完全性。最後,若某 NP 完全語言在 P,算法傳遞便使全部 NP 語言在 P,結合 P 包含於 NP 即得相等。
方向至關重要:要證明新目標困難,應把已知困難來源歸約到新目標。把目標歸約到已知難題,只表示難題求解器可解目標。容易問題也能歸約到難題,所以這個方向不能證明目標困難。
從 3-SAT 到 CLIQUE
設公式有 個子句。每個文字出現位置建立一個頂點,保留子句及位置索引,共 頂點。兩頂點恰在來自不同子句且文字不互補時連邊;不互補指不是同一變量及其否定。相同子句內不連邊。要求的團大小設為 。
證明
(滿足賦值與大小為 的團互相對應)
若公式可滿足,每子句選一個為真的出現位置。任意兩個所選文字同時為真,不可能互補,又來自不同子句,所以全部相鄰,形成 大小團。
反之,團每子句至多取一點,因同子句無邊。至少 點的團於是恰從每子句取一點。所選文字無互補配對,故能一致地指定其變量值令其為真,其餘任意。每子句都有所選真文字,公式遂可滿足。這證明兩個方向,而不只是畫一幅看似合理的圖。
只有 頂點及至多二次數目的候選邊。判斷文字名稱是否互補,對編碼長度為多項式時間,所以整圖可在公式長度的多項式時間內寫出。若無子句,空合取為真,送到固定是實例,例如一頂點、閾值一的圖。格式錯誤則送到固定否實例,令歸約總定義。
CLIQUE 屬 NP:若 ,立即拒絕,不嘗試讀長度 證書;否則證書列出 個互異頂點,檢查互異及每對相鄰均多項式,證書長度也多項式。大於 的團包含恰 點的團,所以證書符合「至少」版本。結合歸約與屬 NP,得到完全性,只依賴已明述的 3-SAT 起點。
證明透視
為甚麼兩條連邊規則缺一不可
這個圖有兩條連邊規則,各司其職。同一子句內不連邊,使團在每個子句中至多取一點,所以大小為 的團必須在每個子句中恰好取一個出現位置;這正好把團轉成「每個子句選一個文字」。互補文字之間不連邊,則使所選文字互相一致,可以用同一個賦值使它們全部為真。
兩條規則都不能去掉。若容許同一子句內連邊,大小為 的團可以在某個子句取幾個出現位置而在另一個子句一個也不取,那個子句便沒有被滿足。若把互補文字連起來,團可以同時含有 和 ,而沒有任何賦值能令兩者皆真。不同子句中同一文字的兩個出現位置是相鄰的,這沒有問題:同時選取它們是一致的。證明最後把所選文字設為真,其餘變量任意賦值。
補圖與頂點集合補集
補圖 保留相同頂點,兩個不同頂點恰在 沒有邊時連邊。某集合在 是團,當且僅當在 獨立。因此 把 CLIQUE 歸約到 INDEPENDENT SET。由頂點明列,建構至多二次數目的邊為多項式。列出頂點並檢查選中各對無邊,證明屬 NP。
證明
(獨立集與頂點覆蓋互為補集)
在同一圖內, 獨立當且僅當 是頂點覆蓋。若 獨立,邊不可能兩端都在 ,所以至少一端在補集;反之,若補集覆蓋全部邊, 不可能內含邊。因此 時,
得到歸約 。若 ,來源為否,可送到只有一邊且覆蓋預算零的固定否實例。頂點覆蓋證書列出不超預算的頂點,再檢查每邊有被列端點。若預算至少 ,自動為是,所以數值預算大也不會要求超多項式證書。這完成頂點覆蓋的成員及困難性證明。
兩次「補」不同:一次改變圖邊,另一次保持圖而改變選中子集。把操作分開寫可防止常見錯誤歸約。
判定、搜尋與最優化
判定預言機只答是或否,搜尋則要求證書。對 CLIQUE,可用多項式次判定調用找團。先問大小 是否可行。若是且 ,考慮某頂點 。若刪 後仍有 團,便刪除並繼續;否則每個 團都用 ,輸出 ,把圖限制在其鄰點,所需大小減一。後者成立是因為團的其餘頂點都必與 相鄰。每步移去至少一頂點或降低需求,保持是實例,所以只作多項式次、不增大圖的調用。
這是自適應預言機算法,不是前面一次輸出實例的多對一歸約;用途也不同,它說明假設有多項式判定算法,此問題便有多項式搜尋算法。求最大團大小可先在零到 間對單調閾值作二分搜尋,再重建該大小團。這些關係需要證明,不能按定義把判定與最優化混用。
例題詳解
例題 4.1.5
(選取一致文字的位置)
取子句 與 。有六個位置頂點,重複的 各有獨立頂點。賦值 可選第一子句的 與第二子句的 ,它們相連。若改選 與 ,則沒有邊。子句歸屬是構造一部分,所以重複名稱不合併頂點。
例題 4.1.6
(獨立集及其覆蓋)
四頂點路徑邊為 ,集合 獨立,其補集 覆蓋每邊。 由內含邊 而不獨立,其補集 也未覆蓋該邊。這以明確可行與不可行選擇驗證集合補集等價。
例題 4.1.7
(偽多項式表沒有解決 P 與 NP)
前篇背包表對每個數值容量設一狀態。具有 位元的二進制容量可接近 ,所以 可對輸入長度為指數。找到此表並未自動給出二進制判定問題的多項式算法。關鍵是編碼區分,並非動態規劃與困難性歸約互相矛盾。
常見錯誤
反例模式
簡單的來源問題不會令目標問題變簡單
聲稱:若 而 CLIQUE 是 NP 完全的,則 是 NP 困難的。取 。把每個輸入都映成只有一個頂點、閾值為 的固定圖(這是 CLIQUE 的「否」例子),就是一個多項式時間多對一歸約 。可是 不是 NP 困難的:NP 含有全體字串的語言 ,而由它到 的歸約 需要對每個 都有 ,這是不可能的。箭頭把算法上的用處倒過來傳遞:快速的目標求解器能幫助來源問題,而快速的來源求解器並不能解任意的目標輸入。要證明困難性,應把已知困難的問題歸約到目標問題。
常見錯誤
(NP 完全性證明漏掉一項要求)
困難性證明須有明確映射、多項式構造及輸出界、正確性兩方向,以及已知難的起點。NP 完全性另須屬 NP。只列看似合理的證書而不限制多項式長度,仍有缺口。
常見錯誤
(把 NP 完全性解讀得過頭)
不可推斷所有 NP 問題均 NP 完全、NP 困難即屬 NP,或 NP 完全性已證 P 不等於 NP。它建立的是條件結論:多項式求解器會使 P=NP;也不自動給出指數下界,不保證某實際實例難。近似品質及特殊圖類別需要另行分析。
總結
NP 描述有界驗證,歸約傳遞假設算法及困難性。從 3-SAT 到 CLIQUE、補圖獨立集、集合補集頂點覆蓋的完整鏈,逐項展示證明責任。計算到公式定理仍是已明述依賴,沒有把省略的一般證明或未解下界當成已建立。
練習
快速檢查
(學生證明了 ( 是 NP 完全的),便宣稱 是 NP 困難的。請以一個簡單的來源語言說明當中的漏洞。)
想一想哪個問題的求解器能幫助哪個問題。
解答 · 答案
這個歸約把 的求解器傳到 ,並沒有證明 困難。例如空語言可以歸約到 CLIQUE(永遠輸出一個固定的「否」例子),但空語言本來就可以立刻判定。要證明困難性,應把已知 NP 困難的語言歸約到 。
練習 4.1.8
(證明當閾值以二進制書寫(包括閾值超過頂點數的情況)時,CLIQUE 仍屬於 NP。)
核心證明
解答(4)
- 1
解析並比較閾值
解析二進制閾值 ,並在多項式時間內把它與頂點數 比較。若 便拒絕,不需要證書。
依據: 兩個數都寫在輸入中。
- 2
定義證書
關鍵一步
對 ,證書列出 個互不相同的頂點編號,需要 個位元。對 ,空證書有效。
依據: 當 時,列表很短。
- 3
檢查證書
所列頂點是否互不相同、是否兩兩相鄰,都可在多項式時間內檢查。
- 4
把證書對應到判定問題
∎大小大於 的團必含大小恰為 的團,所以接受證書存在,當且僅當圖中有至少 個頂點的團。
快速檢查
(對 ,描述歸約所得的圖,並說明它為甚麼沒有大小為二的團。)
檢查哪些出現位置之間有邊。
解答 · 答案
每個子句有三個出現位置頂點,子句內沒有邊。所有跨子句的配對都是互補的,所以也沒有跨子句邊。這個圖是六個孤立頂點,任何兩個頂點都不構成團。公式確實不可滿足,因為它要求 與其否定同時為真。
練習 4.1.9
(證明:若 且 ,則 。)
核心證明
解答(3)
- 1
應用歸約
設 為該歸約。對輸入 ,在多項式時間內計算 ;它的長度至多為 ,其中 為某個多項式。
- 2
重用 的驗證器
關鍵一步
設 (取為不減)與 為 的證書長度界與驗證器。定義 ,並只接受 的證書;這個界至多為 ,是 的多項式。
依據: 的證書長度界用在像 上,而 的長度是 的多項式。
- 3
檢查正確性與執行時間
∎驗證器 以多項式時間運行。由歸約的等價性, 當且僅當 ,當且僅當存在 的證書 使 接受,亦即存在某個短證書 使 接受。所以 。