1985 Richard Karp —— 二十一個問題與歸約的傳染病#

「1972 年，一位伯克利教授在一份機密報告的附錄裡，用一頁 表格把二十一個古典難題串成同一案件。這是理論計算機科學 最著名的一頁。」

案件檔案#

前因#

Cook（1982 案）1971 年證明 SAT 是 NP 完全。當時疑點： SAT 是否只是邏輯學的特例？ 與排程、圖論、數論等實務 問題有何相干？

線索與推理#

線索一：多項式歸約作為「傳染鏈」#

A ≤ₚ B：存在多項式時間函數 f，x ∈ A ⟺ f(x) ∈ B
性質：≤ₚ 傳遞 → SAT 的難度可「轉移」給任何被歸約到的問題

線索二：Karp 的 21 個問題（1972, STOC）#

從 SAT 出發的歸約鏈（節錄）：

SAT ≤ₚ 3-SAT ≤ₚ Clique ≤ₚ Vertex Cover ≤ₚ Set Cover
SAT ≤ₚ 3-SAT ≤ₚ 3-Coloring（圖著色）
SAT ≤ₚ Exact Cover ≤ₚ Hamiltonian Cycle ≤ₚ TSP（判定版）
SAT ≤ₚ Integer Programming、Subset Sum、Knapsack ...

一頁紙的歸約網，證明數十個橫跨圖論、邏輯、數論、 組合的問題共享同一個難度核心——這是複雜度理論的 「大統一時刻」。從此學者不再問「這題難嗎」，而問 「它 NP 完全嗎」。

線索三：不可近似性的先聲#

Karp 晚期工作（與 Papadimitriou、Yannakakis）指向近似 複雜度：NP 完全問題不僅難解，連近似到某精度也難—— 後由 PCP 定理（1992）完成封頂。

線索四：隨機與並行#

Karp 對隨機演算法（如 Rabin 路線的系統化）、以及 P-完全性 （並行難度）皆有奠基貢獻——難度光譜被劃得更細。

理論評析#

Karp 方法的偵探學意義：歸約是「案件併案」的數學形式—— 表面不相干的兇案，若能證明由同一手法（SAT）派生，即屬 同源。NP 完全性不是性質的集合，而是等價類：所有這些 問題在多項式世界裡互相是彼此的化身。

後果#

• 密碼學（2002、2015 案）的安全性假設直接採用「問題難解」 作為公理。
• 精確解不可能 → 近似演算法、啟發式（模擬退火、遺傳）、 SAT 求解器實務翻盤，構成今日的組合最佳化工具箱。

關聯案件#

→ 1982-Stephen-Cook與NP完全性理論、1993-Hartmanis-Stearns與計算複雜度分級定理、1976-Rabin-Scott與非確定性自動機