一個難問題，化作一根撬棍
上一篇結束時，你手裡已握有兩樣東西。從庫克-列文定理而來的，是單一一個問題——SAT——從第一原理被證明為 NP 完全，意思是它既屬於 NP，又至少和 NP 裡的每一個問題一樣難。而從歸約那一篇而來的，是多項式時間歸約，一種藉由「把 A 的任一實例在多項式時間內轉成 B 的等價實例」來宣稱「問題 B 至少和問題 A 一樣難」的辦法。本篇談的，就是把這兩者湊在一起會發生什麼事：一個被證明為難的問題，搖身變成撬開其他成千上萬個問題之難度的撬棍。
這裡有一條關鍵的邏輯鏈，值得放慢腳步細看，因為後面每一個證明都不過是把這條鏈再跑一遍。假設 A 已知為 NP 完全，而你建出一個從 A 到你的新問題 B 的多項式時間歸約。歸約的方向至關重要：一個從 A 到 B 的歸約，顯示的是 B 至少和 A 一樣難——A 是你倚靠的那個難東西，B 是你把它推進去的那個東西。於是 B 繼承了 A 的難；又因為 A 和整個 NP 一樣難，由遞移性，B 也是。這就讓 B 成為 NP 困難。再補上一個「B 自己也屬於 NP」的快速檢查，B 便是 NP 完全：它已加入這個位於該類別正天花板的俱樂部。
證明一個問題為 NP 完全的四行食譜
你日後會讀到或寫出的幾乎每一個 NP 完全性證明，都套用同一個模板。把它的形狀記熟，其餘不過是替你的特定問題填細節。所有的巧思都活在第三步——那個把一個問題的結構轉成另一個問題結構的「小裝置」——但周圍的鷹架始終不變。
- 證明 B 屬於 NP。對任一個是的實例，展示一段簡短的憑證，以及一個會接受它的多項式時間驗證器。略過這一步是個實實在在的錯誤：一個問題可以是 NP 困難卻遠高於 NP，所以光憑「NP 困難」並不能給你「NP 完全」。
- 挑一個已知為 NP 完全的問題 A，作為歸約的來源。挑一個結構上已經和 B 相像的——這個選擇就贏了一半。好的起點包括：對付邏輯約束用 3-SAT、對付圖用頂點覆蓋或獨立集、對付數字裝填用子集和。
- 描述一個多項式時間的映射 f，把 A 的任一實例 x 變成 B 的一個實例 f(x)。這就是那個小裝置：B 裡面的小零件，模仿 A 的變數與子句（或頂點與邊）。f 必須跑在多項式時間內，這同時也限定了 f(x) 能有多大。
- 證明兩個方向的等價：x 是 A 的一個是的實例，當且僅當 f(x) 是 B 的一個是的實例。「僅當」（是映到是）與「當」（否映到否，亦即 f(x) 為是會逼出 x 為是）是兩段各別的論證，而忘掉第二段，正是一個「證明」無聲無息出錯的經典方式。
留意這裡的分工。第一步只關乎 B；第二到第四步關乎那座從 A 過來的橋。多項式時間的界限出現了兩次——在驗證器上，也在映射 f 上——而且兩者都要緊：一個花指數時間的歸約什麼也證明不了，因為它大可在過程中乾脆用暴力法把 A 解掉。整座建築底下那具誠實的引擎，仍然是「P 對 NP」的未決狀態；我們會在結尾回到「這究竟換來什麼、又付出什麼」的確切問題。
一個做過的草圖：3-SAT 到獨立集
我們在一個具體、經典的小裝置上跑一遍這份食譜，好讓抽象落地。取 3-SAT——一個布林公式，其中每個子句都恰是三個文字的 OR，例如 (x OR not-y OR z) AND (not-x OR y OR w)——把它歸約到獨立集：「這張圖有沒有 k 個彼此互不相鄰的頂點？」獨立集屬於 NP（一組被提議的 k 個頂點，要驗證它們兩兩不相鄰再容易不過），所以第一步已完成。現在來看那個小裝置。
Formula: (x OR not-y OR z) AND (not-x OR y OR w)
Gadget: one triangle per clause, vertex = literal
clause 1 clause 2
x not-x
/ \ / \
not-y -- z y ----- w
+ connect EVERY literal to its negation across triangles
(x -- not-x, y -- not-y, ...)
Ask: is there an independent set of size k = #clauses ?這個建構分兩步。第一，對每個子句做一個三頂點的三角形，每個文字一個頂點；因為三者兩兩相鄰，一個獨立集從每個三角形裡至多只能挑一個頂點。第二，在每一個文字與它的否定之間（無論它們出現在哪裡）都連一條邊，這樣你就絕不會同時選中 x 與 not-x。現在令 k 等於子句的數目。建這張圖顯然是多項式的——每個子句不過幾個頂點和幾條邊——所以映射 f 很快。一切都繫於那個等價宣稱，我們現在就把它兩個方向都驗一遍。
正向：若公式可滿足，每個子句至少有一個為真的文字；從每個三角形裡挑出一個為真文字的頂點。那就是 k 個頂點、每個三角形一個，所以沒有任何三角形的邊被違反；又因為一個變數的真值是固定的，我們絕不會同時挑中 x 與 not-x，所以也沒有任何否定邊被違反——一個大小為 k 的合法獨立集。反向：若存在一個大小為 k 的獨立集，它必定是每個三角形恰取一個頂點（k 個三角形、每個至多一個、合計 k 個），而那些否定邊保證了被選文字彼此一致，於是把那些文字設為真便滿足了每個子句。是映到是，而圖為是也逼出公式為是。歸約完成，獨立集是 NP 完全。
那座動物園，以及「身在其中」到底意味著什麼
SAT 一旦被撬開，水壩就潰了。獨立集、頂點覆蓋、團、圖的三著色、漢米頓迴圈、旅行推銷員的決定性問題、子集和與分割、裝箱問題，以及另外數百個，每一個都用你剛建的那種小裝置鏈回了某個已知為難的問題。它們構成一個巨大的等價類——NP 完全動物園——而這種鏈接意味著一件驚人的事：對其中任何一個的多項式時間演算法，藉由把歸約串接起來，就會生出對它們全部、乃至對整個 NP 的多項式時間演算法。它們同生共死。
還有一個比較安靜、值得點名的可能性。有些問題身在 NP、看起來難、卻抵抗著每一個想證明它們為 NP 完全的歸約——這就是被懷疑為 NP 中間 的問題，整數分解與圖同構是著名的候選。倘若 P 不等於 NP，拉德納（Ladner）的一個定理保證這類「住在中間的」必定存在；我們只是無法確鑿地指出某一個。所以這片地景並不是乾淨地分成「簡單的 P」與「難的 NP 完全」兩個桶——中間或許還夾著一層，這又是一個「每句難度宣稱都該謹慎陳述」的理由。
那麼，P 對 NP 究竟意味著什麼？
把神秘感剝掉，P 對 NP 這個問題陳述起來殘酷地簡單：凡是「解容易驗」的問題，是不是也都是「解容易找」的問題？倘若 P 等於 NP，那麼「認得出一個好答案」與「生得出一個好答案」之間的鴻溝，會在所有地方同時崩塌——對 SAT、對被擺成搜尋問題的蛋白質摺疊、對定理證明、對守護你網路銀行登入的那套密碼學，全都如此。倘若 P 不等於 NP——幾乎每位專家都這樣下注——那麼這道鴻溝就是真實而永久的，NP 完全問題也就確確實實、在結構上超出了有效率求解的範圍。無論是哪一種，答案都會重塑計算；而直到今天，沒人知道是哪一個。
現在來到清醒的部分——「把一個問題證成 NP 完全」在實務上替你換來了什麼、又沒換來什麼。它不代表「放棄」。它代表「別再獵尋一個快速的精確、通用、最壞情況演算法」，而把力氣花在仍有進展空間的地方。你或許可以設計一個 近似演算法，保證給出的解落在比方說最佳解的 2 倍之內——不過記得，一個 2-近似是最壞情況的承諾，而非典型情況的承諾。你或許可以利用「真實輸入很小或很特殊」這件事，走參數化或「指數但實用」的方法。又或者你可以倚靠那些通常極好、偶爾很糟的啟發式方法。NP 完全性重新導向了這場搜尋，而非終結它。
退一步，看看這一階給了你什麼。一個對「有效率」的精準定義（多項式時間）、一個對「可驗證」的精準定義（NP）、一個轉移難度的工具（歸約）、一塊親手鋪下的地基石（庫克-列文），以及一份「把新問題鏈回那塊石頭來定罪」的四行食譜。那道誠實的前沿是：核心問題依舊未決——「NP 完全」是我們所知能給出的、關於難解性最強的證據，建立在多項式與指數增長之間的鴻溝上——但它是證據，不是判決。穩穩握住這個區別，既不過度宣稱、也不灰心喪志，這才算是真正理解了這一階。