庫克-列文定理（Cook-Levin theorem）
/ Cook-Levin = kuk-LAY-vin /
每條鏈都需要第一個環節。要證明一個問題是 NP 困難，我們把一個已知困難的問題歸約到它——但「最初的那一個」問題是怎麼被加冕為困難的，明明沒有東西可供歸約？庫克-列文定理就是那個奠基之舉：它從零開始證明布林可滿足性（SAT）是 NP 完全。它是讓整座 NP 完全大廈得以成立的基石；一旦 SAT 困難，其餘一切都能透過歸約從它繼承困難性。
其陳述是：SAT 屬於 NP，「且」NP 中每個問題都在多項式時間內歸約到 SAT。前半很容易（一組可滿足指派就是簡短憑證）。後半才是深刻之處，而證明的構想確實巧妙：取「任一」屬於 NP 的問題 A。依定義，A 有一個多項式時間驗證器 V——其實是一台非決定性機器，吃進輸入 x 與一個猜出的憑證，最多執行 p(|x|) 步。庫克與列文示範如何機械地寫下一個布林公式 F(x)，使它「恰好」在那台機器於 x 上有一條接受計算時可滿足。這個公式的變數描述了整段計算：每一時步每一格紙帶的內容、每一步機器的狀態、讀寫頭的位置。接著由子句強制機器的「物理定律」：起始組態編碼了 x；每一步都遵循機器的轉移規則；不在讀寫頭下的紙帶格不變；而最終狀態是接受的。因此 F(x) 的一組可滿足指派，不外乎就是機器一次合法的接受執行——亦即 x 是「是」實例的證明。所以「x 是 A 的『是』實例，當且僅當 F(x) 可滿足」，而 F(x) 只有多項式多個變數與子句，可在多項式時間內算出。這就是歸約 A <=p SAT，而且一次對「每個」屬於 NP 的 A 成立。
它為何如此重要：這一條定理把 NP 的抽象定義（任何有多項式驗證器的東西）轉化成單一個具體問題 SAT，而它被證明和整個類別一樣難。在它之後，證明新問題為 NP 完全便不再需要對整個 NP 推理——你只要把 SAT（或它的子代 3-SAT）歸約到你的問題即可。歷史是個有趣的註腳：史蒂芬・庫克於 1971 年證明了它；列昂尼德・列文在蘇聯獨立證明了等價結果，因而有了這個合稱。一個誠實的附註：公式 F(x) 是「從」驗證器的描述建構而來，所以證明之所以成立，是因為「有一個多項式驗證器」本身就是一個精確、可機械化的陳述——這條定理其實談的是「把一段計算編碼成邏輯」。
勾勒一台小機器的編碼：引入變數 T[i, t, s] 意為「在時間 t，紙帶第 i 格存著符號 s」，以及 Q[q, t] 意為「在時間 t 機器處於狀態 q」。子句說：在 t = 0 時紙帶拼出 x；每一格要嘛維持不變、要嘛恰好依某轉移規則改變；每一步恰有一個狀態；而在最終步狀態為「接受」。這個公式可滿足，當且僅當存在一條合法的接受執行。
F(x) 把整段計算編碼成邏輯；一組可滿足指派『就是』一次接受執行。
庫克-列文定理是啟動 NP 完全動物園的引子：它是唯一一個「不靠從先前困難問題歸約」就證出的困難性結果。之後每個「X 是 NP 困難」的證明都站在這第一個環節上，把 SAT（或 3-SAT）歸約到 X，而不必重跑那套組態表格論證。