歸約：比較難度

我們要伸手去抓什麼，以及為何是現在

到目前為止，本階已給了你兩塊大拼圖。你見過了決定性問題，以及 P 類（能被快速判定）與 NP 類（給一段簡短憑證，「是」的答案就能被快速「核對」，即使找出那段憑證似乎需要指數搜尋）。你也看過了驗證器這幅圖：NP 恰好是那些「是」的實例都帶著一段微小證明、可被某個多項式時間核對者接受的問題。前兩篇談的都是孤立的「單一」問題。本篇要引入的工具，讓我們把問題彼此「相互比較」——而難解性的整套理論，正是住在比較裡，而非孤立裡。

歸約要回答的問題是這樣的。你手上有兩個問題 A 和 B，兩個都沒有快速演算法。它們是「一樣」頑固，還是其中一個其實更難？若能不解開任何一個就把這件事敲定——直接把它們的難度連結起來——那會很美妙。歸約正是做這件事：它是一種把一個問題的實例巧妙轉成另一個問題實例的方法，巧妙到第二個問題的求解器能免費地交給你第一個問題的求解器。一旦你能像這樣搬運「可解性」，你就能依難度替問題排序——而那個排序，正是本階接下來一切的脊椎。

多項式時間歸約的精確形狀

令 A 和 B 都是決定性問題（每個實例都有一個是／否的答案）。一個從 A 到 B 的多項式時間歸約，是一個可在多項式時間內計算的函數 f，它把 A 的每個實例 x 映射到 B 的某個實例 f(x)，並帶著一個鐵一般的承諾：x 是 A 的「是」實例若且唯若 f(x) 是 B 的「是」實例。那個「若且唯若」就是整場遊戲的關鍵。它意味著 f 在雙向上都保住答案——是映到是、否映到否——所以讀出 B 在 f(x) 上的答案，字面上就是讀出 A 在 x 上的答案。我們把這寫成 A <=p B，讀作「A 歸約到 B」。

取 A 的任意一個實例 x——什麼都可以，你必須處理每一種情況。
執行 f 來建出 B 的實例 f(x)；這個建構過程相對於 x 的規模只能花多項式時間。
想像一個（假想的）B 的多項式時間求解器在 f(x) 上回答是或否。
把那個答案原封不動地當作 x 的答案回傳——這是對的，因為 f 遵守「是若且唯若是」的承諾。
下結論：一個多項式時間的 B 求解器，包進 f 裡，就是一個多項式時間的 A 求解器。

箭頭指向哪一邊？

這是整個主題裡最常被弄反的一個想法，所以讓我們小心地把它釘死。一個歸約 A <=p B 說明的是 B 至少和 A 一樣難——而非反過來。感受其原因最乾淨的方式，是沿著兩個方向追蹤後果。「好消息從 B 流向 A」：若 B 結果是容易的（多項式），那麼 A 也是，因為我們解 A 的方式是翻譯到 B、再用 B 的快速求解器。「壞消息從 A 流向 B」：若已知 A 是難的，那麼 B 也必定難，因為若 B 容易，A 就會透過 f 繼承那份容易——這和 A 已知的難度矛盾。所以你從一個你已信任為難的問題「出發」，歸約「到」你想定罪的那個問題。

兩個結構性事實，讓歸約能當作一種排序來使用。其一，歸約是「可遞移的」：若 A <=p B 且 B <=p C，則 A <=p C，因為你能把兩個翻譯器接起來，而多項式時間函數的合成仍是多項式時間。這就是讓難度能沿著一長串問題接力傳遞的原因。其二，歸約尊重類別的邊界：若 A <=p B 且 B 屬於 P，則 A 也屬於 P。這兩個事實都倚靠同一個樸實的工程要點——把一個多項式套在另一個多項式外面仍是多項式——而這正是我們堅持翻譯器 f 必須在多項式時間內執行、一刻也不能更慢的原因。

一個做過的微型歸約：3-SAT 歸約到頂點覆蓋

抽象的說法只能走到這裡；讓我們建一個真正的 f。取 3-SAT（一個每子句三個文字的布林可滿足性公式：是否存在一組真／假指派讓每個子句都為真？），把它歸約到頂點覆蓋（給一張圖和一個數 k，是否有 k 個頂點碰到每條邊？）。這個翻譯分兩塊來建一張圖。對每個變數 x，加一個「小裝置」：兩個頂點，一個標 x、一個標 not-x，用一條邊相連——一場微小的拔河，逼覆蓋恰好挑這一對中的一個，藉此編碼一個真假值。對每個子句，加一個由三個頂點構成的三角形，子句裡每個文字對應一個頂點。

variable gadget (per variable x):     x ---- not_x      (1 edge)
clause gadget (per clause):       a triangle on its 3 literals
wiring:   join each clause-vertex to its matching variable-vertex
set the budget:   k = (#variables) + 2 * (#clauses)

建構 f：每變數一條邊、每子句一個三角形、連接邊，以及一個精挑的預算 k。

現在把連線收尾、把預算定好。把每個子句頂點連到背負相同文字的那個變數頂點。然後要求一個大小為 k = （變數個數）+ 2*（子句個數）的覆蓋。為何恰好是那個 k？覆蓋一個三角形至少需要它三個頂點中的 2 個，而覆蓋每條變數邊至少需要 1 個——所以 k 是可能的最緊預算。把它花掉就逼出處處乾淨的選擇：每個變數裝置一個為真的文字，而每個三角形裡你「省得起」不放進覆蓋的那「一」個頂點，必須由變數那側被覆蓋，意思就是它的文字為真。一個大小為 k 的覆蓋存在，恰好當每個子句都有一個被滿足的文字時——也就是恰好當公式可滿足時。「是若且唯若是」的承諾成立，而整張圖在公式長度的多項式時間內被建好。

誠實的細項說明，以及這要往哪去

幾則誠實的提醒。其一，一個歸約只連結 A 與 B；單憑它本身什麼絕對的事都證不了。「B 至少和 A 一樣難」是一個「有條件」的陳述——只有當你已信任關於 A 的某件事時才有用。無條件的力量在下一篇到來，那時庫克-列文定理供給了第一個對「整個」NP 都被證明為難的問題（SAT），給每個歸約一個堅實的錨可以推。其二，答案保持必須在「雙」向上都精確：一個只保證「是蘊含是」、卻讓 A 的某個「否」實例變成 B 的「是」實例的翻譯器是壞的，因為這樣 B 的求解器會在 A 該說否的地方說是。寫出反方向，通常正是真正的工夫與真正的臭蟲所在。

其三，一個常見的陷阱：歸約不必「自然」、甚至不必有洞見，只要正確且為多項式時間就好。我們的 3-SAT 到頂點覆蓋的小裝置看起來像個任意拼湊的怪機器，那沒關係——公式和圖在直覺上毫無關係，但 f 誠實地搬運了答案。也別把歸約能扮演的兩種角色混為一談。在這座階梯較早處，你看過用歸約在比較模型裡的具體問題之間搬運下界；這裡它搬運的是「對某個複雜度類別的歸屬」以及相對難度的概念。同樣的邏輯動作——便宜地翻譯、保住答案——只是「便宜」與「難」換了一種貨幣。

退後一步，看看你現在握有的槓桿。有了歸約作為難度比較器，單一個難題就不再是一個孤立的事實：每一個「從」它出發的歸約，都把它的難度蓋印到一個新目標上。下一篇把這件事推到戲劇化——NP 困難意味著「NP 裡每個問題都歸約到我」，而庫克-列文定理證明了 SAT 正是這樣一個普世的著陸點。從那一顆種子，一條像你剛建的那種歸約鏈，把難度推遍整個 NP 完全動物園，一舉定罪上千個問題。歸約是那條輸送帶；本階其餘部分講的就是帶上載著什麼。