Cook-Levin 定理（Cook-Levin theorem）
/ Cook -> KUK; Levin -> LEH-vin /
Cook-Levin 定理是整個學科的奠基石。它解開一個雞生蛋的謎題：NP 完全是靠「從一個已知 NP 完全的問題歸約」來證明的，但「第一個」是哪來的？Cook（1971 年）與 Levin（獨立地）證明了布林可滿足性問題 SAT 是 NP 完全。它是最初的錨點；其他每個 NP 完全證明最終都回溯到它。
定理說 SAT 是 NP 完全，而困難的那一半是證明 SAT 是 NP 困難：「每個」NP 問題都歸約到 SAT。其想法是把整段計算編碼成一條邏輯公式。取任一帶有非確定型多項式時間機器的 NP 問題。它跑多項式時間，會填滿一張由格子組成的表格：每個時間步、每個紙帶方格上是什麼符號、讀寫頭在哪、機器處於什麼狀態。我們建出一條巨大的布林公式，其變數描述這些格子，子句強制一個合法的開始、相鄰步驟間的合法轉移（機器的局部「窗格」規則）、以及一個接受的結尾。這條公式可滿足，當且僅當機器有一段接受的計算，也就是恰恰當輸入是「是」實例時。關鍵是這條公式有多項式大小，且在多項式時間內建成。
令人屏息的一著是：可滿足性的邏輯豐富到足以模擬「任何」多項式時間驗證器。一旦 SAT 被釘定為 NP 完全，Karp 就藉由把 SAT（或 3-SAT）歸約到它們，證明了數十個自然問題是 NP 完全，這份清單如今已數以千計。所以 Cook-Levin 定理不只指認出一個難題；它認證 SAT 為 NP 的普世最難問題，是整片 NP 完全問題森林由之生長的種子。
編碼概要：變數 x[i, j, s] 表示「在時間 i，紙帶格 j 上是符號 s」。子句規定每格恰持有一個符號、讀寫頭與狀態依機器的轉移規則跨步演進、且最終格局為接受。一個滿足賦值「就是」一段接受的計算，所以一個 SAT 求解器就能解出原來的 NP 問題。
Cook-Levin：每段 NP 計算都能寫成布林公式，所以 SAT 是 NP 完全，是第一個完全問題。
Cook-Levin「並未」證明 P 不等於 NP。它證明 SAT 是 NP 完全，這是關於歸約的結構事實。SAT（從而整個 NP）是否真的很難，仍未解決。