1982 Stephen Cook —— NP 完全性的偵破：一個等式分割整個計算宇宙#

「1971 年，一位多倫多教授在 ACM 座談會上提出一個問題， 為什麼全世界十幾年來都答不出來——而且答不出來本身就是 最重要的答案？」

案件檔案#

前因#

1960s 的實務怪象：排程、地圖著色、整數規劃……許多問題 「能驗證卻難求解」，最佳演算法指數爆炸。疑點：這是巧合， 還是同一個深層病灶？ Levin（蘇聯）與 Cook 各自逼近同一真相。

線索與推理#

線索一：兩個類別的定義#

P   = 多項式時間可「解」的判定問題
NP  = 多項式時間可「驗證」的問題（憑證 certificate 存在即接受）
      另一等價觀點：非確定性圖靈機多項式時間可解
顯然 P ⊆ NP。逆命題 P = NP 是否成立？——無人知曉

線索二：Cook 定理（1971）#

SAT（布林可滿足性）是 NP 完全的：

定理：L ∈ NP ⟺ L ≤ₚ SAT
證明骨架：對任意 NP 機器 M 與輸入 x，構造布林的「 tableau 」
  變數 T[i,j,s] = 「時刻 i、帶格 j 的符號是 s」
  子句群強制：每格恰一符號、轉移合法、初態/接受態正確
  ⟹ M 接受 x ⟺ 該 CNF 可滿足，且構造為多項式大小

單一問題成為萬問題的投影幕：任何 NP 問題都可多項式 歸約到 SAT。

線索三：Karp 的 21 題（1972）與多項式歸約#

Karp（1985 案）展示 21 個經典問題（Clique、Hamilton 迴路、 整數規劃……）全部 ≤ₚ SAT。歸約的傳染性：

A ≤ₚ B 且 B ∈ P ⟹ A ∈ P
若任一 NP 完全問題 ∈ P ⟹ P = NP

線索四：為什麼「未解」本身就是證據#

千禧年大獎難題之一。普遍猜想 P ≠ NP： - 對角化與電路下界等技術屢屢碰壁（自然證明障礙，Razborov–Rudich） - 若 P=NP，密碼學（2002 案）崩塌、創造性計算崩塌——世界 「看起來」不像那樣

後果#

• 演算法設計的新分類學：多項式 / 指數 / 近似 / 隨機 / 參數化。
• SAT 求解器（DPLL→CDCL）反諷地成為實用工具：晶片驗證、 航班排程皆用之——難解的問題，被暴力到變得有用。

關聯案件#

→ 1985-Richard-Karp與NP完全問題的證明、1993-Hartmanis-Stearns與計算複雜度分級定理、2023-Avi-Wigderson與去隨機化及複雜度理論