在 NP 裡找出一個「最難」的問題，究竟是什麼意思？
到現在，本階的各塊拼圖都已攤在桌上。NP 是這樣一類問題：它的「是」答案附帶一張簡短的憑證——一個提示——而一個驗證器能在多項式時間內檢查它，就像一幅拼好的拼圖，難拼卻易於確認。而從上一篇你帶來了一個多項式時間歸約，一位翻譯員，把一個問題的實例如此忠實地轉成另一個問題的實例，以致解開後者就等於解開前者。一個問題若是 NP 裡的每一個問題都能歸約到它，它就是 NP 困難；若它既是 NP 困難、本身又落在 NP 之內，它就是 NP 完全。NP 完全問題在一個精確的意義下是 NP 中最難的問題：只要在多項式時間內攻破其中任何一個，整個類就垮了。
但這裡藏著一個雞生蛋、蛋生雞的問題，值得停下來想想。要證明一個新問題是 NP 完全的，你把一個已知的 NP 完全問題歸約到它——這是便宜又可重複使用的招數。但第一個 NP 完全問題沒辦法這樣得到，因為沒有更早的問題可以拿來歸約。總得有人把那件難事做一次：直接地、從零開始地證明，NP 裡的每一個問題——全部無窮多個，包括還沒有人命名的那些——都能歸約到某一個特定的問題。那個英雄式的第一個證明，就是庫克-列文定理（Cook-Levin theorem），由 Stephen Cook（1971）與 Leonid Levin（約莫同時）各自獨立證出，而它所加冕的問題，就是布林可滿足性。
認識 SAT，鎂光燈下的那個問題
布林可滿足性，簡稱 SAT，問的問題連初學者都懂。給你一個布林公式，由變數（各為真或假）、連接詞 AND、OR、NOT 與括號構成——例如 (x1 OR NOT x2) AND (x2 OR x3)。問題很單純：存不存在某一組把真／假指派給各變數的方式，使整個公式求值為真？若有，這公式就是可滿足的；那組讓它為真的指派就是答案。以上面的例子來說，令 x1 = 真、x2 = 假、x3 = 真，會讓兩個子句都為真，所以它是可滿足的。就形式定義而言，SAT 並不要求你找出那組指派——只問是否存在一組——而這正是一個判定問題所需的「是／否」形狀。
先看簡單的一半：SAT 穩穩地屬於 NP。憑證就是那組讓公式為真的指派——一張真／假值的清單，每個變數一個，長度不超過公式本身。驗證器把這些值代入並對公式求值，這顯然是多項式時間的工作。所以若答案是「是」，就總有一張簡短、可快速檢查的提示存在。這就坐實了它對 NP 的歸屬。難的那一半——庫克與列文真正得去掙到的部分——是證明 SAT 是 NP 困難的：其餘每一個 NP 問題都向它低頭。
證明的核心構想：一個敘述計算過程的公式
真正巧妙的構想在這裡，而你不必碰那些繁瑣的記帳就能領會。任取 NP 裡的任何問題 A。依本階稍早給過的 NP「非決定性觀點」，A 由某台非決定性圖靈機 N 來判定，而 N 對長度為 n 的輸入至多執行某個多項式步數——比方說 n^k 步。庫克與列文示範如何機械地、在多項式時間內，造出單一一個布林公式，它的變數刻劃 N 的一整次執行，而它恰好在 N 對該輸入存在一次接受性執行時可滿足。這個公式就是一位翻譯員（一個歸約），把「N 接不接受這個輸入？」翻譯成「這個公式可不可滿足？」。解開 SAT，你就解開了 A。
一個靜止的公式怎能捕捉一個動態的計算？把機器的執行想成一張格子表——一張 tableau——每個時間步一列、每個帶格一格，像把翻頁動畫的每一幀並排攤開。格 (t, i) 記下時間 t 時帶格 i 上是哪個符號、讀寫頭在哪、以及機器處於哪個狀態。我們為每一種可能的「(格子, 內容)」組合發明一個布林變數：若在這次執行中該格真的裝著那份內容，變數就為真。這張格子表大致是 n^k 乘 n^k，所以變數數量是多項式級的——而這份多項式大小，正是這個歸約之所以能在多項式時間內完成的全部理由。
- 起步（第一列誠實無欺）：用一些子句強迫格子表的最上列拼出機器正確的起始組態——輸入寫在帶上、讀寫頭在最左、機器處於起始狀態。
- 合理性（每一格都講道理）：用一些子句說每一格恰好裝著一種符號-狀態組合——不是零種、也不是兩種——好讓這張格子表描述的是真實的快照，而非胡言亂語。
- 推移（每一列都從上一列得出）：用一些子句強制任意一個 2 乘 3 的格子小窗都服從 N 的轉移規則——未來是現在合法的後果，一步接一步。N 的程式就是在這裡被烤進公式裡的。
- 接受（故事善終）：用一個子句要求格子表中某處出現接受狀態。如此一來，公式可滿足，若且唯若 N 存在某一次合法且接受的執行。
為何這個構造是忠實的——以及它替我們換來了什麼
魔法就在那個「若且唯若」。公式的任何一組讓它為真的指派，都被那四族子句強迫去描述 N 的一次合法計算——正確起步並抵達接受——所以一組讓公式為真的指派就是一次喬裝過的接受性執行，這意味著 N 接受。反過來，若 N 有一次接受性執行，只要照著格子表讀出來、把每個變數設成相符的值即可；所有子句都會被滿足。N 會做的那些非決定性「猜測」，就成了 SAT 在挑選指派時被允許自由做出的選擇。這就是 SAT 與非決定性彼此契合得像鑰匙插進鎖孔的深層原因：一組讓公式為真的指派，恰恰就是一次猜中了的幸運猜測。
Tableau for a poly-time NDTM N on input w (rows = time, cells = tape squares) t=0 : [q0,a] [ b ] [ a ] [ _ ] ... <- START clauses force this to be N's initial config t=1 : [ x ] [q3,b] [ a ] [ _ ] ... \ t=2 : [ x ] [ y ] [q3,a] [ _ ] ... > MOVE clauses: every 2x3 window obeys delta(q, s) ... / t=T : ... [q_accept, .] ... <- ACCEPT clause: accepting state appears somewhere variable X[t,i,s] = true means "cell (t,i) holds contents s" formula PHI = (START) AND (SANITY: one symbol per cell) AND (MOVE) AND (ACCEPT) PHI is satisfiable <=> N has an accepting run on w <=> w is a YES-instance of A
有兩個誠實的提醒，免得這聽起來像天上掉餡餅。其一，庫克-列文造出的公式雖大，卻是對輸入呈多項式的——然而那多項式可能帶著沉重的指數與龐大的常數，所以這個構造是一座理論的橋，而非快速的實用編譯器；大 O 記號把那些常數藏起來了。其二，原始公式是一個一般的布林公式，但要把它揉成合取範式、再揉成3-SAT（每個子句恰好三個文字）並不難，依然在多項式時間內。那個更整潔的 3-SAT，才是人人在往下歸約時真正會去拉的那根槓桿——例如你下一篇會遇到的、從 3-SAT 到團問題的教科書歸約。
為何單單這一個定理改變了一切
退一步，感受一下這份槓桿。庫克-列文之前，「這問題看起來很難」只是一句抱怨。之後，我們有了一個錨：一個可證明至少和 NP 中一切同樣難的問題。而錨會利滾利。要把一個全新的問題加冕為 NP 完全，你不必再重做一次格子表論證——你只要在多項式時間內把 3-SAT（或另一個已知的 NP 完全問題）歸約到你的新問題，NP 困難性就會自動流過這座橋，因為多項式時間歸約是可複合的。每一次征服都成了下一次的彈藥。這就是 1971 年的一顆種子如何在短短幾年內，長成 Richard Karp 那張 21 個 NP 完全問題的清單，接著再長成數以千計的問題。
這裡還埋藏著一份令人吃驚的統一性。數以千計來自天差地遠世界的問題——電路設計、蛋白質摺疊、排程、益智遊戲——全都是 NP 完全的，這意味著它們全是同一個問題換上不同的戲服，彼此之間只隔著一道多項式翻譯。其中任何一個的快速演算法，都會立刻給出它們全部的快速演算法，並會以肯定的方式了結 P 對 NP。五十多年來沒人找到任何一個，這是「P 大概不等於 NP」最強的非正式證據（並非證明！）。在有人從任一方向證出它之前，誠實的立場是：這仍然開放，而所謂的「明智下注」也只是猜測。