1972-Karp21題#

案件摘要#

1971 年，Cook 證明 SAT 是 NP-complete，但當時這只是「一個問題的孤案」。Richard Karp（UC Berkeley）在 1972 年發表《Reducibility Among Combinatorial Problems》，一口氣用歸約（reduction）證明了 21 個組合問題全是 NP-complete，宣示「難解是普遍現象」。這篇論文把複雜性理論從單點突破變成一張蔓延的傳染網，徹底改寫了演算法學界的辦案手法。本案追查的，正是這場「多項式時間瘟疫」如何散播。

前因 -- 為什麼會有這個案子#

Cook 1971 年證明 SAT（布爾可滿足性）是 NP-complete：任何 NP 問題都能在多項式時間內歸約到 SAT。但當時只有這一個問題被證明，許多人懷疑這只是 SAT 的特殊性。
學界懸案：旅行商問題（TSP）、圖著色、整數規劃等大量組合問題，數十年來無人找到高效演算法，但也無人能證明它們必然困難。
Karp 的直覺：「如果 NP-complete 只是孤立現象，為什麼這麼多看起毫不相干的問題都同樣難解？」他猜想難解性會透過歸約互相傳染。
歸約的數學基礎已備：多項式時間歸約（Karp 歸約，即多一歸約）作為問題之間的偏序關係，具備傳遞性。
1972 年 Complexity of Computer Computations 論文集徵稿，給了 Karp 一次攤牌的機會。

線索與推理 -- 數學式、程式、理論#

多項式歸約與傳遞性#

問題 \(A\) 多項式歸約到問題 \(B\) （記作 \(A \leq_p B\) ）定義：存在多項式時間可計算函數 \(f\) ，使得

\[ x \in A \iff f(x) \in B \]

傳遞性是整場瘟疫的傳染途徑：

\[ A \leq_p B,\quad B \leq_p C \quad \Rightarrow \quad A \leq_p C \]

因為 \(f_C \circ f_B\) 是兩個多項式時間函數的合成，仍為多項式時間。於是只要 SAT 是 NP-complete，且 \(SAT \leq_p X\) ，則 \(X\) 也是 NP-complete。證明難解性的負擔，從「對每個問題構造通用的模擬」簡化為「對每個問題設計一個轉換函數」。

Karp 的 21 題：歸約樹#

Karp 的論文是一棵歸約樹，根是 SAT，分支展開（節點順序即歸約方向）：

SAT
├── 0-1 整數規劃
│      └── （整數規劃反過來也吸收各種問題）
├── Clique（最大團）
│      ├── Set Packing（集合裝填）
│      └── Vertex Cover（頂點覆蓋）
│             └── Set Cover（集合覆蓋）
├── Hamiltonian Cycle（漢密爾頓圈）
│      ├── Hamiltonian Path（有向/無向）
│      └── （經由「元件設計」吸收多種圖問題）
├── 3-SAT（之後再用它攻擊更多問題）
│      ├── Chromatic Number（圖著色）
│      ├── Exact Cover（精確覆蓋）
│      └── feedback vertex set 等一批問題
├── Exact Cover
│      ├── Subset Sum / Partition（分割）
│      │      └── Sequencing / Knapsack（背包）等
│      └── 3-dimensional matching（三維匹配）
└── Steiner Tree、Max Cut、Scheduling 等其餘問題

代表性歸約一例： \(SAT \leq_p \text{Clique}\) ——對公式中每個文字出現處建一個頂點，同一子句內的頂點連邊、互為補文字的頂點不連邊；公式可滿足當且僅當圖有大小等於子句數的團。

Gadget Construction：歸約的構造技巧#

歸約的藝術在於 gadget（小裝置）：在圖中嵌入一段局部結構，強迫任何最優解「必須」以某種特定方式使用它。例如 Vertex Cover 歸約中，把每條變數選擇編碼成「二選一的邊」，把每個子句編碼成「三角形」，使得覆蓋頂點數恰好 \(\leq k\) 當且僅當存在滿足賦值。這種「用組合結構模擬邏輯電路」的手法，成為日後數千題 NP-complete 證明的標準劇本。

程式碼示範：3-SAT → Vertex Cover 的 gadget 建構#

以下 Python 程式實作經典的 3-SAT → Vertex Cover 歸約：每個變數一條「選擇邊」（選 T 或 F 端點），每個子句一個三角形 gadget；並附暴力驗證（小規模下直接檢查覆蓋條件）。

from itertools import product

def sat_to_vertex_cover(clauses):
    """clauses: list of clauses, each clause = [lit1, lit2, lit3],
    literal = (var, bool). 回傳 (edges, k)。"""
    edges, k = [], 0
    vars_ = sorted({v for c in clauses for v, _ in c})
    # 變數 gadget：一條選擇邊 (v_t, v_f)，必須覆蓋其一
    for v in vars_:
        edges.append((f"{v}:T", f"{v}:F"))
        k += 1
    # 子句 gadget：三角形，三個頂點各連到對應文字端點
    for i, c in enumerate(clauses):
        tri = [f"C{i}:{j}" for j in range(3)]
        edges += [(tri[j], tri[(j + 1) % 3]) for j in range(3)]
        for j, (v, val) in enumerate(c):
            edges.append((tri[j], f"{v}:{'T' if val else 'F'}"))
        k += 1
    return edges, k

def has_cover_of_size(edges, k, n_vertices):
    from itertools import combinations
    verts = sorted({u for e in edges for u in e})
    if n_vertices is not None:
        verts = verts[:n_vertices]
    for cover in combinations(verts, k):
        s = set(cover)
        if all(u in s or v in s for u, v in edges):
            return True
    return False

def brute_sat(clauses):
    vars_ = sorted({v for c in clauses for v, _ in c})
    for assign in product([False, True], repeat=len(vars_)):
        env = dict(zip(vars_, assign))
        if all(any(env[v] == val for v, val in c) for c in clauses):
            return True
    return False

clauses = [[("x1", True), ("x2", True), ("x3", False)],
           [("x1", False), ("x2", False), ("x3", True)],
           [("x1", True), ("x2", False), ("x3", False)]]

edges, k = sat_to_vertex_cover(clauses)
print("SAT 可滿足?      ", brute_sat(clauses))
print("覆蓋大小 <= k 存在?", has_cover_of_size(edges, k, None), "(k =", k, ")")

兩行輸出恆為同一真值——這就是歸約正確性的破案時刻。

NP-complete 的「傳染性」#

一旦一個問題被證明 NP-complete，所有能歸約到它的問題自動獲得「同等嫌疑」。Karp 的 21 題像 21 個感染源；此後新問題只要歸約到任一已知 NP-complete 問題即可結案。P vs NP 之謎也隨之聚焦：只要任一 NP-complete 問題找到多項式演算法，全部 21 題（乃至所有 NP）同時解決。

結案 -- 後果與影響#

NP-complete 目錄爆發式擴張：1979 年 Garey 與 Johnson 的《Computers and Intractability》已收錄數百題，至今累積數千題。
歸約成為複雜性理論的標準武器：證明難解性、證明下界、密碼學的安全性歸約，全部沿用同一手法。
哲學轉折——近似演算法的誕生：「既然最優解多半難求，就退而求多項式時間內的近似保證」，開啟了近似比、PTAS、APX-hard 等整個研究領域。
參數化複雜度、隨機化演算法等後續領域，也都以 Karp 歸約為起點。
Karp 於 1985 年獲圖靈獎，表揚其對演算法理論的持續貢獻。

關鍵人物與文獻#

Richard M. Karp, "Reducibility Among Combinatorial Problems", in R. E. Miller & J. W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, 1972, pp. 85-103.
Stephen A. Cook, "The Complexity of Theorem-Proving Procedures", Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC), 1971, pp. 151-158.
Michael R. Garey & David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
Richard M. Karp, "On the Computational Complexity of Combinatorial Problems", Networks, 5(1), 1975, pp. 45-68.