從比較難度到一個最難的問題
在上一篇導覽中，一個從問題 A 到問題 B 的多項式時間歸約給了我們一句口號：若 A 歸約到 B，則 B 至少和 A 一樣難，因為任何 B 的快速解法都能變成 A 的快速解法。那個箭頭指向固定的方向——解出 B 就能解出 A——所以它替這兩個問題排了名。現在問問這份排名引出的大膽問題。在那些「肯定答案都帶有一張簡短、可檢驗的憑證」的問題所組成的類別 NP 之內，是否存在某個單一問題，坐在最頂端——一個讓其他每個 NP 問題都歸約到它的問題？若真有這樣的冠軍存在，那麼它在實質意義上就是 NP 中最難的問題：在多項式時間內攻破它，就一口氣攻破了 NP 中的一切。
兩個詞彙把這件事釘牢。一個問題 B 是 NP困難 的，如果 NP 中的每個問題都能在多項式時間內歸約到它——B 至少和 NP 中的一切一樣難，無論 B 本身是否屬於 NP。一個問題是 NP完全 的，如果它既是 NP困難、又是 NP 的成員。所以 NP完全同時意味兩件事：難到整個 NP 都灌進它裡頭，卻又馴到本身擁有簡短的憑證。NP完全問題恰恰是那些仍然屬於 NP 的最難問題，而一個我們會反覆使用的美妙事實是：它們全都同生共死。
為何攻破一個難題就推倒一千個
在見到第一個 NP完全問題之前，先細品這個定義替我們買到了什麼，因為它正是整個主題的引擎。假設 B 是 NP完全的，而有人找到了 B 的多項式時間演算法。取 NP 中任何另一個問題 A。由 B 的 NP困難性，A 在多項式時間內歸約到 B：轉換 A 的輸入、跑那個快速的 B 解法、讀出 A 的答案——全是多項式的，所以 A 現在落在 P 中。但 A 是任意一個 NP 問題。所以單單一個 NP完全問題的多項式演算法，就會證明 P = NP，把整個類別坍縮掉。骨牌早已預先排好；推倒任何一張 NP完全的骨牌，就推倒了全部。
其逆否命題才是研究者每天真正倚賴的版本。如果 NP 中哪怕只有一個問題確實落在 P 之外——如果 P 不等於 NP，一如幾乎所有人所相信的——那麼任何 NP完全問題都永遠不可能有多項式演算法。這就是為何證明你的問題是 NP完全的，是如此有力的消息。它並非字面上證明了不存在快速演算法，畢竟 P 對 NP 尚未解決；但它確認了你的問題，恰恰和成千上萬個著名問題一樣難——那些問題，一支由聰明絕頂的人組成的大軍，五十多年來都未能加速。在實務上，那就是你的許可證：可以停止獵尋一個精確的多項式方法，轉而設計近似法、啟發式、或僅僅是優於暴力法的指數方法。
庫克-列文定理：第一個最難的問題
這裡有個雞生蛋的卡關。要用歸約證明一個新問題是 NP完全的，我們得把一個已知的 NP完全問題歸約到它——但那需要手上先有一個 NP完全問題，而此刻還沒有任何東西可供歸約。庫克-列文定理 從零打破了這個循環。它證明了 布林可滿足性——SAT，那個決定性問題「給定一個由真／假變數構成的布林公式，是否存在一組賦值使它為真？」——是 NP完全的。這是整座 NP完全動物園的種子：第一個在沒有任何前輩可依靠的情況下，被證明為 NP 中最難的問題。
證明 SAT 在 NP 中是容易的那一半：一組可滿足的賦值就是一張簡短的憑證，而把它代入並計算公式是一次快速的檢查——恰恰是本階稍早的驗證器圖像。深刻的那一半是證明 SAT 是 NP困難的：NP 中的每一個問題都歸約到 SAT。我們無法把那些問題一個一個列舉出來；它們有無窮多個。所以庫克與列文從 NP 的定義本身出發歸約。每個 NP 問題，依定義，都有一個多項式時間的驗證器——一個固定的機械程序，給它輸入加上一張候選憑證，它跑多項式步數後輸出是或否。
訣竅是把那個驗證器的整段執行，捕捉成單一個巨大的布林公式。想像驗證器的計算被攤成一張方格表：列是時間步、行是記憶體格，而每個方格裡裝著一個符號。局部規則規定一列如何由前一列得出——一小套固定的接線，到處重複——而那些規則，加上「輸入是固定的」與「最後一步說接受」，就翻譯成一些布林子句，其變數描述著每個方格。所構造的公式為可滿足，恰恰當某張憑證使驗證器接受時。所以原始輸入是肯定實例，當且僅當該公式可滿足，而整張方格表只有多項式大小，因此這項構造在多項式時間內執行。那就是一個從任意 NP 問題到 SAT 的多項式時間歸約。
從 SAT 出發，動物園靠歸約壯大
一旦 SAT 成為錨點，雞生蛋的問題就永遠消失了，而下一篇導覽將倚賴這一點。要證明一個全新的問題 X 是 NP完全的，你不再需要從整個 NP 歸約——你只做兩件有限的工作。先藉由展示一張簡短的憑證與一個快速的驗證器，證明 X 在 NP 中。然後挑任何一個已知為 NP完全的問題，在多項式時間內把它歸約到 X。因為歸約會接龍——它們是遞移的——那單單一次歸約，就默默地透過那個已知問題繼承了整個 NP，而那個已知問題又是透過 SAT 繼承來的。
- 庫克-列文從第一原理證明 SAT 是 NP完全的，方法是把任何多項式驗證器編碼成一個布林公式。
- SAT 歸約到 3-SAT（每個子句恰有三個文字的公式），所以 3-SAT 也是 NP完全的——而它規整的形狀使它成為後續歸約最受青睞的起點。
- 3-SAT 歸約到圖問題、排程問題、裝箱問題，如此一路下去；每一次新的歸約都為 NP完全大家庭添一個成員，全都繼承了 SAT 的難度。
成千上萬個自然的問題就是這樣被掃進這個家庭的，而下一篇導覽會完整地建構出這樣一個歸約。每一個都是 NP完全的，所以每一個都是下一個證明的有效新錨點；這座動物園自我增強。而每位成員都共享同一個命運：它們之中任何一個的多項式演算法，都把它們全體放入 P，而證明它們之中任何一個需要超多項式時間，就把它們全體擋在 P 之外。正是這份共享的命運，使「NP完全」成為一個融貫的單一判決，而非一個鬆散的標籤。
誠實的附帶細則，以及 P 對 NP 究竟在問什麼
把四個提醒帶在身邊。其一，「NP完全」不代表「已被證明沒有多項式演算法」。 它代表的是：目前無人知道有，而找到一個就會把 P 對 NP 坍縮掉——那是一個著名的開放問題，而非一個已了結的判決。其二，NP完全談的是最壞情況：一個問題可以是 NP完全的，卻擁有一些、甚至大多數能快速求解的實例；許多真實的 SAT 公式在幾毫秒內就破了。其三，光是 NP困難並不能把一個問題放進 NP，所以在宣稱完全性之前，務必檢查它是否屬於 NP。其四，歸約的方向毫不留情：要證明你的問題 X 很難，你必須把一個已知很難的問題歸約「到」X，絕不能反過來；把 X 歸約到某個容易的東西，對 X 的難度什麼也證明不了。
握有了 NP完全性，我們終於能精確地陳述那個頭條問題。P 對 NP 問的是：找出一個解，是否和檢查一個解一樣容易？P 是我們能快速求解的問題；NP 是我們能快速檢查其候選解的問題。庫克-列文表明 NP 有一層頂樓——那些 NP完全問題——而 P = NP 將意味著那層頂樓並不比 P 高，意味著每個可快速檢查的問題也都可快速求解。幾乎所有人都押注 P 不等於 NP，押注有些問題確實檢驗起來比發現起來更容易，但五十年過去，無論哪個方向都還沒有證明。
留意 SAT 暴露出的不對稱，最後一篇談 co-NP 的導覽會把它磨利。SAT 的一個肯定答案，附帶一組你能瞬間檢查的可滿足賦值——一張簡短的憑證。但一個否定答案意味著根本沒有任何賦值奏效，而對「不可滿足」並沒有顯而易見的簡短憑證；你似乎得排除每一組賦值才行。便宜的「是」之證明與看似昂貴的「否」之證明之間的這道縫隙，正是 NP 與它的鏡像 co-NP 分道揚鑣之處，也是 P 對 NP 問題如此深刻又如此頑固的又一個緣由。