Karp 21 — 21 个 NP-完全问题

是什么

1972 年，Richard Karp 用 cook-levin 的归约技术证明了：21 个看起来毫不相关的组合问题——旅行商、子图同构、3-着色、最大团、装包……——其实全部一样难，都是 NP-完全。

日常类比：你面前摆 21 把锁，看起来花纹各异。Karp 拿一把万能钥匙挨个试了一遍，证明这 21 把锁的锁芯其实是同一种。只要造得出能开任意一把的钥匙，所有 21 把都能开。可惜过去 50 多年没人造得出——这就是 NP-完全。

具体说，Karp 证明的是：

已知 SAT（布尔可满足性）是 NP-完全（Cook 1971）
21 个常见组合问题都能”翻译”成 SAT，多项式时间内完成
所以这 21 个问题也是 NP-完全

为什么重要

不理解 Karp 21，下面这些事都没法解释：

为什么”旅行商”和”芯片寄存器分配”听起来八竿子打不着，却用同一类求解器能跑
为什么 1972 年之前运筹学家相信”再多写几个启发式总能找到 P 算法”，1972 年之后改口”这条路可能永远走不通”
为什么你拿到一个新优化问题，只要它”长得像” 21 之一就基本判死刑（多项式时间不可解）
为什么 Garey-Johnson 1979 那本《NP-Complete Cookbook》列出 300+ NPC 问题——Karp 21 是种子

简单说：Karp 让 NP-完全从”理论里的一个孤岛”变成”现实里的一片群岛”。这 21 个加上后续衍生，覆盖了工业界大约 90% 的”难解优化问题”。

核心要点

Karp 论文的核心机器是 多项式时间归约，三件事拼起来：

归约（reduction）：写一个多项式时间的”翻译器” f，把 A 问题的实例翻译成 B 问题的实例，且”A 有解 ⟺ B 有解”。意味着如果 B 有快算法，A 也有。记作 A ≤ₚ B。
链式传递：归约可以串起来。SAT ≤ₚ 3-SAT ≤ₚ Clique ≤ₚ Vertex Cover……一条链下去，每一节都继承”NP-完全”标签。
家族图谱：Karp 不是孤立证 21 次，而是构造了一棵”归约树”——根是 SAT，每个内部节点已知 NPC，每片叶子顺着归约链上来也 NPC。一棵树搞定 21 个证明。

类比：你有 21 道菜想测是不是同一种辣度。你不用每道都直接试舌头，只要证明”道 A 翻译过去 = 道 B”，链式传递就够了。Karp 的厨房里 21 道菜都翻译到了 SAT。

实践案例

案例 1：SAT → 3-SAT 的归约

3-SAT 是”每个子句恰好 3 个 literal 的 SAT”。看起来比一般 SAT 简单，其实一样难。

证明思路：把任意长子句切成多个 3 子句。例如 4-子句 (x ∨ y ∨ z ∨ w) 引入新变量 a，拆成：

(x ∨ y ∨ a) ∧ (¬a ∨ z ∨ w)

原 4-子句可满足 ⟺ 新两个 3-子句可满足（双向验证）。多项式时间完成翻译。

这是”形式约束 → 形式约束”的归约，最简单的一种。

案例 2：3-SAT → Clique 的归约

把布尔公式翻译成图：

每个 3-子句对应图里 3 个顶点（每个 literal 一个）
两个顶点连边，当且仅当：来自不同子句 + 不互为否定（x 和 ¬x 不连）

那么 “3-SAT 公式 φ 有 m 个子句可满足” ⟺ “构造的图有大小 m 的派系（clique）”。

这次归约的优雅在于：把”逻辑约束”翻译成”图的连通约束”。两个领域看起来毫无关系，归约把它们钉在了一起。后续 21 个归约几乎都是这种”找两个问题的结构同构”。

案例 3：现代工业怎么用

工业界遇到陌生优化问题，通常套路是：

判断它”长得像” 21 之一吗？（整数变量 + 线性约束 = 0-1 ILP；图上找最大子集 = Clique；选最少集合覆盖 = Set Cover……）
如果像，转成那个问题，丢给现成求解器
求解器是 MILP solver（Gurobi / CPLEX / SCIP / Cbc）或 SAT solver（Z3 / MiniSAT / Kissat）
求解器内部用 LP 松弛 + 分支定界 + 切平面 + 启发式硬怼，工业实例几秒到几分钟搞定

worst case 仍然指数（NP-完全没破），但工业实例分布”友好”，求解器修了高速公路。

踩过的坑

NP-完全 ≠ “实际上无解”：很多 NPC 问题在工业实例上能秒解。Knapsack 有 FPTAS，TSP 有 1.5-近似，MAX CUT 有 0.878-近似。NPC 是”最坏情况”标签，不是”永远难”。
归约不保留近似比：Karp 归约证明判定难度等价，不保证近似难度等价。MAX CUT 几乎可解到信息论最优，CLIQUE 几乎不可近似——它们都是 NPC。误把”同一标签”读成”同一难度”是 1972 之后 20 年的盲区，PCP 定理（1992）才修正。
“是 NPC 就放弃”是智识陷阱：很多 NPC 问题在受限图族（平面图、弦图、有界 treewidth）上是 P 的；参数化复杂性（FPT）下也常常实际可解。每次见到 NPC 标签至少应问”参数化呢？""平均情况呢？""受限输入呢？”。
“多项式时间归约”不是”快”：归约本身可以耗 n^100 时间，仍然算多项式。理论意义重大，工程意义有限。归约树告诉你”这些问题等价”，没告诉你”实际跑哪个最快”。

适用 vs 不适用场景

适用：

判定一个新优化问题是否 NP-完全（找一个已知 NPC 问题归约过去）
设计求解器架构时对问题统一建模（CP-SAT / MILP / SMT 都是这个思路）
选近似算法 / 启发式策略时知道下界在哪
教学：理解”为什么这些问题难”

不适用：

单纯比较”哪个 NPC 问题在工业实例上更快”——Karp 归约不告诉你
推断”近似难度”——要用近似保持归约 / PCP
量子算法分析——Grover 给 √n 加速，归约树不变但难度地图变
平均情况复杂度——Karp 归约只管 worst case

历史小故事（可跳过）

1971 年：Stephen Cook 发表《The Complexity of Theorem-Proving Procedures》，证明 SAT 是历史上第一个 NP-完全问题。学界反应：“好奇怪的理论玩具，跟工业里 scheduling / routing 没关系。”
1972 年：Richard Karp 把孤岛炸成群岛——一篇论文里把 21 个常见组合问题归约到 SAT。运筹学家、图论学家、调度学家一夜之间发现”我们做的是同一件事”。
1979 年：Garey & Johnson 出版《Computers and Intractability》，收集 300+ NPC 问题。这本书被工业界叫做 NP-Complete Cookbook，至今还是查 NPC 问题的圣经。
1992 年：PCP 定理完成，把 Karp 归约升级成”近似保持归约”。从此 NPC 问题的”近似难度”成为独立学科。
2001 年起：精细复杂性（ETH / SETH）兴起，把”NPC 标签”细化成”指数下界”。Karp 论文从此成为所有计算复杂性课的第一周必读。

学到什么

归约是计算复杂性的核心思维——把陌生问题翻译成已知问题，链式传递难度。这思维在数学、密码学、机器学习里都通用。
标签会麻痹——“NPC” 本来是地形地图（最坏情况），被很多人当判决书（永远难）。每次看到标签都要问背后的细分。
理论 → 工程，每一步隔几十年：1971 Cook → 1972 Karp → 1979 Cookbook → 1990s MIP solver 工业化 → 2008+ Gurobi 性能爆发。每一步都不是”理论突破”而是”工程积累”。
同一标签 ≠ 同一难度：Karp 归约保留判定难度，不保留近似难度 / 参数化难度 / 平均情况难度。这是 1972 之后 50 年精细复杂性的研究主线。
一篇论文造一个领域是历史常态：Karp 让本来分散在 OR / 图论 / 调度的研究者突然意识到他们做的是同一件事，这种”做版图”工作往往比单独算法贡献更深远。
3-SAT vs 2-SAT 的临界：3-SAT NPC 而 2-SAT 是 P，差只在子句长度 +1。复杂性结论是”参数变一点结果天差地别”，没有”看起来差不多就一样难”。
NPC 不等于无解：实务里 SAT solver / MIP solver 在中等规模实例上常能秒级返回——“理论最坏指数” 与”工程平均可解” 是两个独立结论，悲观看复杂性会错过工业 solver 的真实能力。

关联

cook-levin —— Cook 1971 证 SAT 是第一个 NPC，Karp 用它当根
turing-1936 —— 计算理论的源头，可计算性 → Karp 接力到复杂性
godel-1931 —— 不完备性给”形式系统有界限”开第一枪，Karp 给”高效算法有界限”开同一类的枪
hindley-milner —— 类型推导的”可判定性”也站在 P/NP 的边界上

反向链接

cook-levin —— Cook-Levin 定理 — NP-完全性的诞生
dijkstra-shortest-path —— Dijkstra 最短路径 — 一杯咖啡时间想出来的贪心算法
gin-2019 —— GIN — 把图神经网络的表达力顶到理论天花板
godel-1931 —— Gödel 1931 — 不完备性定理
goldsmith-1987-bvh —— Goldsmith-Salmon 1987 — 让计算机自己给场景搭层次包围盒
hindley-milner —— Hindley-Milner — 编译器自己猜变量类型
lsh-indyk-1998 —— LSH — 让相似点撞同一个桶，把高维最近邻查询从线性变成亚线性
turing-1936 —— Turing 1936 可计算性