多項式時間歸約與 NP 困難性

同一個翻譯員，新的貨物：難度

你在這座階梯稍早遇過歸約，當時它是用來轉移「辦不到」的：若我能把停機問題翻譯成你的問題，那你的問題也必定不可判定，因為它的求解器就能解我們已證明無解的停機問題。歸約是一位翻譯員——一份配方，把問題 A 的每一個實例忠實地轉成問題 B 的一個實例，使得「是」對應到「是」、「否」對應到「否」。在這一階，我們留著同一台機器，只換掉貨物。我們不再轉移「不可能」，而是轉移「看來非常難」。如今這位翻譯員必須夠便宜，便宜到它不可能偷偷在背地裡把真正的活兒幹了。

關鍵的新約束在這裡。從 A 到 B 的一個多項式時間歸約（也叫 Karp 歸約，或多對一映射歸約）是一個函數 f，它在輸入大小上以多項式時間可計算，並且使得 x 是 A 的「是」實例，若且唯若 f(x) 是 B 的「是」實例。為什麼 f 必須在多項式時間內跑完？因為若允許翻譯員花指數時間，它就能在一旁偷偷把難題解掉、再吐出一個瑣碎的答案——這份翻譯就把難度偷渡進「翻譯這個動作」本身，什麼也證明不了。逼 f 必須是多項式的，能讓它保持誠實：它只被允許重塑問題的形狀，絕不被允許去回答它。

方向就是一切（再說一次）

這裡最常見的單一錯誤就是歸約方向反了，所以讓我們把箭頭朝哪走講到狠清楚。假設你想證明某個新問題 NEW 很難。你必須把一個已知很難的問題歸約進 NEW，也就是 KNOWN <=p NEW。這句話的意思是：「若 NEW 很容易，那 KNOWN 也會很容易」——而既然我們相信 KNOWN 很難，NEW 就也必定很難。倘若你反過來做 NEW <=p KNOWN，你只證明了 NEW 不會比那個已知的難題更難，這是個真確卻無用的事實：一個問題可以既容易、又不會比某個難題更難。難度只朝一個方向流動，從你信得過它很難的來源，流向你正在指控的目標。

還有兩個性質，讓這些歸約足以當作一種難度的「通貨」。第一，它們可以串接：若 A <=p B 且 B <=p C，則 A <=p C，因為一個多項式翻譯員接著另一個跑，整體仍是多項式（多項式套多項式還是多項式）。所以難度會沿著鏈條滑行，就和不可判定性當初一樣。第二，多項式時間歸約尊重 P 類：若 B 在 P 中且 A <=p B，那 A 也在 P 中——先翻譯、再求解，兩步都便宜。這第二個事實就是一切的引擎：一旦某一個 NP 困難問題被發現能用多項式時間解掉，所有歸約到它的問題就會跟著它一起塌進 P。

NP 困難與 NP 完全：兩個定義，分開來看

現在我們能精確地替這兩個角色命名了，而它們很容易被搞混，所以請把它們分開握著。一個問題 H 是 NP 困難（NP-hard）的，若 NP 中的每一個問題都在多項式時間內歸約到它——H 至少和 NP 裡的一切一樣難。注意 H 自己甚至不必在 NP 之內；它可能難得多，或根本不是一個判定問題。一個問題是 NP 完全（NP-complete）的，若它既是 NP 困難又是 NP 的成員。所以 NP 完全 = 仍住在 NP 之內的那些最難的問題——同時奪冠者：和 NP 裡任何東西一樣難，卻仍配備了 NP 成員資格所要求的、那份簡短而能在多項式時間內驗證的憑證。

這就引出一個雞生蛋的煩惱。要證明一個新問題 NP 困難，我們把一個已知 NP 困難的問題歸約進它——但在還沒有任何東西被認定為難之前，我們是怎麼拿到那第一個的？這正是Cook-Levin 定理的任務，也是下一篇的主題：它從 NP 的赤裸定義出發，直接證明了布林可滿足性（SAT）是 NP 完全的，做法是展示任何一台非確定性驗證器的計算都能被編碼成一個邏輯公式。SAT 是那顆種子。一旦我們有了這個錨點，往後每一個 NP 完全性證明，都只是一個（直接或透過一條鏈）從 SAT 出發的多項式時間歸約。

真正動手造一個：3-SAT 歸約到 clique

在你親眼看著一個歸約被造出來之前，定義都還停留在抽象。所以讓我們建構那個經典的：3-SAT 歸約到 clique（團）問題。3-SAT 問的是：一個合取範式（每個子句恰有三個文字）的布林公式，能否被某個指派弄成真。clique 問題問的是：一張圖裡是否含有 k 個兩兩相連的頂點（一個大小為 k 的團）。這兩個問題看起來像住在不同宇宙——邏輯對上圖論——然而一個多項式時間的翻譯員，能把任何一個 3-SAT 公式變成一張圖，使得圖中的團恰好對應到使公式為真的指派。這座橋是一個小裝置（gadget）：一小片圖的碎片，模仿來源問題的某一個零件。

讀進公式。假設它有 k 個子句，每個子句是三個文字（一個變數或它的否定）的一組，例如 (x OR y OR not z) AND ...。對每個子句裡的每個文字，往圖裡放一個頂點。一個有 k 個子句的公式給出 3k 個頂點，分成 k 個小三元組。
在兩個頂點之間連一條邊，僅當它們位於不同子句中，而且它們不互相矛盾——也就是說，其中一個不是另一個的否定（絕不把 x 連到 not-x）。刻意地在同一子句的三元組內部不連任何邊。
現在用 k =（子句數）去問 clique 問題。論斷：這個公式可滿足，若且唯若這張圖含有一個大小為 k 的團。
看看「唯若」為何成立：一個使公式為真的指派，會讓每個子句裡至少有一個文字為真。在每個子句各挑一個這樣的真文字——那是 k 個頂點，每個三元組一個。其中沒有任何兩個互相矛盾（一個真文字和它的否定不可能同時為真），而且它們落在不同子句，所以所有需要的邊都存在。它們構成一個 k-團。
再看「若」的方向：一個 k-團必定從每個三元組各取恰好一個頂點（三元組內部沒有邊，所以同一子句的兩個頂點絕不可能同時在團裡）。把每個被選中的文字設為真；既然被選的文字裡沒有兩個互相矛盾，這就是一個一致的指派，而且它滿足每一個子句。兩個方向都成立，所以這個歸約是忠實的。

Formula:  (x OR y OR z)  AND  (NOT x OR NOT y OR z)     k = 2 clauses

Clause 1 triple:   [x]   [y]   [z]
Clause 2 triple:   [!x]  [!y]  [z]

Edges: connect across clauses, skip contradictory pairs (x--!x, y--!y).
   [z](c1) -- [z](c2)        ok (not contradictory)
   [x](c1) -- [!y](c2)       ok
   [x](c1) -- [!x](c2)       NO  (contradiction)
   ...

A 2-clique = pick one true literal per clause that don't conflict,
e.g. z(c1)--z(c2)  ==>  set z = true  ==>  both clauses satisfied.

這個歸約的縮小版。翻譯員只是檢視並複製結構——數子句、比對文字——這些顯然都能在「公式長度的多項式」時間內完成。它從不嘗試去滿足公式本身。

讀懂歸約證明了什麼——以及沒證明什麼

那個小小的建構到底替我們換到了什麼？既然 3-SAT 是 NP 完全的（它透過更早的一個歸約繼承了 SAT 的難度），而 3-SAT <=p clique，那 clique 問題就是 NP 困難的。而 clique 自己也在 NP 之內——給定一個聲稱的團，你只要檢查它所有的頂點對都相連即可，這是從一份簡短憑證出發的快速驗證。NP 困難加上身在 NP 之內，就意味著 clique 是 NP 完全的。同樣的小裝置手法向外擴散：clique 歸約到頂點覆蓋（圖中大小為 k 的團，對應到補圖中大小為 n 減 k 的頂點覆蓋）、3-SAT 歸約到三著色、到漢米爾頓路徑、到子集和，再到旅行推銷員問題。每一條連結都用一個量身打造的小裝置，而它們合起來織成了那張著名的 NP 完全問題之網，你會在最後一篇導覽它。

不過對極限要誠實。歸約證明的是相對難度，絕非絕對難度。它說的是「clique 至少和 3-SAT 一樣難」，而這句話的意義，只取決於我們相信 3-SAT 很難這件事——而這份信念，建立在「P 是否等於 NP」這個至今仍未解的問題上。沒有人證明過任何 NP 完全問題需要超過多項式的時間；那是個猜想，不是定理。還有兩個值得隨身帶著的警告：一個多項式歸約仍可能把輸入放大一個多項式倍率，所以「多項式」不等於「免費」；而一個帶著像 O(n^100) 這種怪獸指數的多項式時間演算法，技術上算易處理，實務上卻毫無用處——記得 big-O 是對最壞情況增長率的上界，不是對真實世界速度的保證。

還有一個迷思要徹底埋葬：量子電腦並不已知能有效率地攻破 NP 完全問題。量子機器對某些有結構的問題（如質因數分解）有幫助，但質因數分解一般不被認為是 NP 完全的，而且沒有人知道任何能有效率地解 SAT 或 clique 的量子演算法。所以當你面對的問題被驗明是 NP 完全時，務實的反應不是去等待奇異的硬體。而是去因應它：退而求一個近似的答案、倚靠那些儘管有最壞情況上界、卻在真實實例上跑得飛快的啟發式方法與現代 SAT 求解器，或是利用某個一直保持很小的小參數。歸約正是我們最初得以認出這整個家族的方式——而認出它，正是在告訴你：別再追獵一個完美的快速演算法，開始聰明地因應吧。