1971 - Karp 的 21 個問題：NP-complete 泛濫#
案件摘要#
1971 年，Richard Karp 在論文〈Reducibility Among Combinatorial Problems〉中，用多項式歸約把 SAT 的「NP-complete」標籤一次性傳染給 21 個經典組合問題——3SAT、Clique、Vertex Cover、Set Cover、Hamiltonian、TSP、Subset Sum、Partition、整數規劃等。NP-complete 從孤立案例變成一場席捲組合數學與運籌學的瘟疫。
前因 -- 為什麼會有這個案子#
1971 年 Cook 剛證明 SAT 是 NP-complete，但當時反應冷淡：
- SAT 是邏輯問題，運籌學家與組合數學家覺得「與我無關」；
- TSP、背包問題等已有幾十年研究史，充滿漂亮的演算法與下界技巧，大家相信「再努力一點就能找到好演算法」。
Karp 的偵探直覺是：
如果歸約具有傳遞性，那麼 SAT 的難度可以沿著歸約鏈傳播到任何問題。讓我畫出這張傳染地圖。
線索與推理 -- 數學式、程式、理論#
線索一：多項式歸約 \(\leq_p\) 的定義#
定義： \(L_1 \leq_p L_2 \iff\) 存在多項式時間可計算函數 \(f: \Sigma^* \to \Sigma^*\) 使得
定理（傳遞性）： \(L_1 \leq_p L_2 \wedge L_2 \leq_p L_3 \implies L_1 \leq_p L_3\) 。
證明：合成 \(g = f_2 \circ f_1\) ；多項式合成多項式仍多項式（ \(O(n^{a}) \to O(n^{ab})\) ）。 \(\blacksquare\)
定理（完備性傳染）：若 \(C\) 是 NP-complete 且 \(C \leq_p X\) 、 \(X \in \text{NP}\) ，則 \(X\) 也是 NP-complete。
這就是 Karp 的方法論：只需一次歸約，就給一個問題定罪。
線索二：Karp 的 21 個問題清單#
Karp 展示的歸約鏈（判定版問題，括號內為現代慣稱）：
SAT ──→ 3SAT ──→ Clique (團)
│
├──→ Vertex Cover (點覆蓋)
│ │
│ └──→ Set Cover (集合覆蓋)
│ └──→ Hitting Set, ...
└──→ Exact Cover (精確覆蓋)
└──→ Hamiltonian Circuit (漢密爾頓圈)
├──→ Hamiltonian Path
├──→ TSP (判定版)
└──→ Directed Hamiltonian
3SAT ──→ 0-1 Integer Programming (整數規劃)
3SAT ──→ Chromatic Number (著色)
3SAT ──→ Feedback Arc Set / Feedback Vertex Set
SAT ──→ Matching (偽多項式)/Knapsack (背包) ──→ Subset Sum (子集和)
└──→ Partition (分割)
另含: Max Cut, Set Packing, Steiner Tree, Job Shop Scheduling ...
21 個問題包括：SAT, 3SAT, Clique, Set Packing, Vertex Cover, Set Cover, Feedback Vertex Set, Feedback Arc Set, Directed Hamiltonian Circuit, Undirected Hamiltonian Circuit, 0-1 Integer Programming, Chromatic Number, Clique Cover, Exact Cover, Hitting Set, Steiner Tree, 3D Matching, Knapsack, Job Scheduling, Partition, Subset Sum。
歸約鏈的數學結論：若任何一個有多項式演算法，則 整條鏈全部有：
線索三：Python 演示 3SAT→Clique 歸約#
構造：給定 3SAT 公式 \(\varphi\) 有 \(m\) 個子句 \(C_1,\dots,C_m\) 。為每個子句的每個文字建一個頂點（共 \(3m\) 個）；若兩頂點來自不同子句且文字不衝突（ \(x_t\) 與 \(\neg x_t\) 不同時出現），連一條邊。則：
原因：大小 \(m\) 的團必須每個子句恰好選一個文字，且互不衝突——這正是「一致的賦值」。
def sat_to_clique(clauses):
"""3SAT -> Clique 歸約：回傳 (邊集, 目標團大小)"""
edges = []
verts = [(i, lit) for i, c in enumerate(clauses) for lit in c]
def conflict(a, b): # x 與 ¬x 衝突
return a == -b
for a in verts:
for b in verts:
if a[0] != b[0] and not conflict(a[1], b[1]):
edges.append((a, b))
return edges, len(clauses)
clauses = [[1, -2, 3], [-1, 2, -3], [2, 3, -1]]
edges, k = sat_to_clique(clauses)
print(f"頂點 3*{len(clauses)}=9 個, 邊 {len(edges)} 條, 找大小 {k} 的團")
# 從團中每個子句取一個文字即可還原出滿足賦值
歸約函數本身（建頂點與邊）只需 \(O(m^2)\) 時間——多項式，定罪成立。
線索四：Subset Sum / Partition 與偽多項式#
Karp 鏈中還有數值問題：
Subset Sum：給定整數集 \(S = \{a_1, \dots, a_n\}\) 與目標 \(t\) ，問是否存在子集使 \(\sum_{a \in T} a = t\) ？
它是 NP-complete，但有一個 \(O(n \cdot t)\) 的動態規劃——時間依賴數值 \(t\) 而非其位數 \(\log t\) ，故稱偽多項式（pseudo-polynomial）。因 \(t < 2^{\log t}\) ，偽多項式演算法在位數尺度下是指數的：
這解釋了為何 Knapsack 實務上「好用」卻在理論上「難」——除非 \(\text{P}=\text{NP}\) ，不存在真多項式（強多項式）演算法。
結案 -- 後果與影響#
- NP-complete 泛濫成時代現象：到 1979 年 Garey & Johnson 的書已收錄數百個 NP-complete 問題；今日已逾數千。
- 運籌學、圖論、排程、密碼學的諸多核心問題被定罪，學界接受「設計近似演算法/啟發式/參數化演算法」是正道：近似比 \(\rho\) 、PTAS、FPT 等領域應運而生。
- 歸約證明成為理論計算機科學的標準文體——像數學中的「定理-證明」一樣。
- Karp 清單中的問題至今仍是演算法課程的必修案例（Vertex Cover 的 2-近似、Set Cover 的 \(O(\log n)\) 近似、TSP 的 Christofides 1.5-近似等）。
- Karp 因貢獻獲 1985 年圖靈獎；此論文被譽為「理論計算機科學被引用最多的論文之一」。
關鍵人物與文獻#
- Richard M. Karp（Berkeley）：〈Reducibility Among Combinatorial Problems〉, in Complexity of Computer Computations (Miller & Thatcher eds.), Plenum Press, 1972（報告於 1971 年研討會）。
- 前驅：Cook (1971) SAT NP-complete；Edmonds (1965) good algorithm。
- 後續：Garey & Johnson《Computers and Intractability》(1979)；Ladner (1975) NP 中間問題；Papadimitriou《Computational Complexity》(1994)。
- 圖靈獎：1985 年（Karp）。