似曾相识燕归来
貌虽不一，却似她三分
先来看看定义
归约（Reduction）第一次看有点像数学家在劝人认输：这题太难了，减一减吧。
算法里的意思倒更像转接。手里来了一个陌生问题 U，我们恰好认识另一个问题 V，甚至已经有了能解决 V 的算法。于是找一个翻译函数 f，把 U 的实例送去 V 的世界。
当然，转接不能乱接。原题明明有解，翻译过去却变成无解，那叫篡改题意；原题无解，翻译完忽然皆大欢喜，也不行。
正式一点。对两个判定问题 U 和 V，如果存在函数 f，使得：
- U 的每个实例 x 都能被构造成 V 的实例 f(x)； - x 是 YES instance，当且仅当 f(x) 也是 YES instance； - f(x) 可以在多项式时间内算出；
我们就说 U 可以多项式归约到 V，记作：
整份定义的心脏只有这一行：
题目的衣服随便换。公式可以换成图，排班可以换成布尔变量，旅行路线也可以被塞进整数规划。真假不能换。
本文说的归约，具体指多项式时间 many-one reduction，也叫 Karp reduction：把输入整体翻译一次，再交给目标问题。Turing reduction 则宽松得多，它允许算法在运行中多次询问目标问题，像带着一个随叫随到的 oracle。两者都叫 reduction，权限并不一样，证明时最好先看清题目发的是哪张通行证。
f 也不用追求一一对应。好几个 U 实例可以挤进同一个 V 实例，V 里也可以住着一大群永远不会被 f 访问的实例。我们只查两件事：
1. 这趟翻译跑得够不够快； 2. 翻译前后的答案有没有变。
如果我们已经有一个解决 V 的算法，那么面对 U 时，可以先计算 f(x)，再把翻译后的实例交给 V 的算法：
所以：
表达的是 U 不比 V 更难，或者反过来说，V 至少有 U 那么难。
这根箭头很短，杀伤力很大。后面很多证明的生死，就悬在它朝哪边。
---
把陌生问题送进熟悉的接口
先看一个没那么学术的场景：晚宴上来了一群互相看不顺眼的人，主办方希望把他们分到若干桌，任何一对有矛盾的人都不能同桌。
“人际关系如何妥善安置”听起来很像一门需要终身修习的学问。先别修，画图：
- 每个人是一枚顶点； - 两个不能坐一起的人之间连一条边； - 每张桌子是一种颜色； - 相邻顶点不能同色。
人情世故被拿掉以后，桌上只剩一个图着色问题。算法不认识前任、甲方和宿敌，它只看见“相邻顶点不得同色”。
这也是归约常见的工作方式。现实问题来的时候总是裹得很厚：行业术语、人物关系、业务背景，一层又一层。可以先让它过一次数学安检：
外套脱了，术语放筐里，约束条件一个个拿出来。
供应链排班、芯片布线、社团分组和匹配系统，拆到最后可能共用同一副骨架。领域知识依然重要，它告诉我们哪些约束不能丢；而归约负责辨认，这副骨架以前是否见过。
古人讲“名”与“实”，名称流转，结构未必随之改变。归约把这件事写得更硬：每个实例怎么过去，要交代；过去之后真假是否照旧，也要交代。
问题没有凭空变简单，只是终于露出了可以下手的地方。
---
多项式时间——翻译费不能比原题还贵
翻译也要花时间。
假如我们声称已经把难题 U 归约到了熟悉的 V，仔细一看，函数 f 自己先跑了指数时间，这个“算法”大概长这样：
我有一个高效解决难题的方法：先用四十万亿年把题目翻译一下。
假设一个问题有 100 个布尔变量，暴力枚举共有
种赋值。即使每秒检查十亿种，也需要约 4.0 × 10¹³ 年。NASA 给出的宇宙年龄约为 138 亿年；换句话说，等你枚举完，宇宙年龄这把尺子已经用了接近三千遍。
所以“多项式”三个字不能省。它同时管着两件事：
1. f 的计算时间要受输入规模的多项式约束； 2. f(x) 的长度也不能爆炸式增长。
第二点其实被第一点暗中照看着：一个普通的顺序算法若只跑多项式步，本来也写不出指数长度的输出。但证明时把实例规模单独说清楚，读者会安心很多。
还有一种归约，形式上无懈可击，实际上偷偷把整道题做完了。比如：
这段描述在逻辑上成立，却没有提供可执行的归约。它相当于：
如何赚到一亿元？先确认你已经有一亿元。
归约函数只能根据输入进行构造，不能预先调用原问题的答案。检查这一点时，可以问一句：
构造 f(x) 的过程中，是否已经暗中解决了 x？
这句话很朴素，也很适合在考试最后五分钟救命。
---
箭头方向——复杂度理论的单行道
归约箭头经常反直觉。先别背，跟着算法走一遍。
已知：
如果 V 有多项式时间算法，那么：
1. 用多项式时间把 U 的实例变成 V 的实例； 2. 用多项式时间解决 V； 3. 得到 U 的答案。
于是 U 也在 P 中。
箭头从 U 指向 V，意思是 U 可以把自己的活交给 V 做。能接住这份活的 V，难度至少不会低于 U。
现在想证明一个新问题 W 很难。我们需要找来一个已有 NP-complete 认证的老前辈 K，然后把它送进 W：
如果画成反方向：
我们得到的只是 W 不比 K 更难。W 也许困难，也许相当温和，这条归约没有告诉我们。
我最常用的记法是：
要证明谁难，箭头就指向谁。
也可以想象公司甩锅：谁能完整接走一项任务，谁就至少扛得住这项任务的全部麻烦。复杂度理论很少谈办公室政治，箭头倒是画得相当诚实。
---
归约为什么可以连成一条链
单条归约已经很有用，更厉害的是它们可以接起来。
假设：
先用 f 把 U 的实例翻成 V，再用 g 翻成 W。两位译者都靠谱，接力也就靠谱：
真假沿途没有丢：
两个多项式时间函数复合起来仍是多项式时间，于是：
复杂度结论便能沿着链条一路传下去。Cook 从 SAT 点起一盏灯，后来的归约把这束光接到 Clique、Vertex Cover、Hamiltonian Cycle 和许多现实问题上。
顺便记两条性质：
- 自反性：问题可以用恒等函数归约到自己； - 传递性：U ≤ₚ V 且 V ≤ₚ W，就有 U ≤ₚ W。
两个问题还可能互相归约。此时它们在多项式时间这把尺子下处于同一难度等级，长相和解法则完全可以南辕北辙。复杂度理论看骨，不看脸。
---
心理学里的归约——识别隐藏的共同结构
人类解决问题时，也会进行一种较为松散的跨领域映射。心理学把这种能力称为类比迁移（analogical transfer）。
Gick 与 Holyoak 在 1980 年的经典研究中，让参与者解决“放射线问题”：
医生要用射线摧毁肿瘤。高强度射线能摧毁肿瘤，却也会伤害沿途的健康组织；低强度射线安全，却不足以摧毁肿瘤。怎么办？
另一个故事讲的是攻占堡垒：
大军走同一条路会触发地雷，于是将军把军队拆成许多小队，从不同道路同时抵达堡垒。
两个故事分别来自医学与军事，表面元素相距很远，约束结构却高度一致：
实验里，只看到放射线问题时，大约 10% 的参与者找到了解法；先读过堡垒故事后，成功率约为 30%；当研究者明确提示“前面的故事可能有用”时，成功率升到约 75%。
提示没有增加新的领域知识，它帮助参与者检索并识别了两个问题之间的结构映射。这组数据说明：拥有一个相关解法，与能在新情境中调用它，是两件不同的事。
许多看似全新的问题，可能只是采用了陌生的表述。
人的记忆容易沿着表面特征检索：医院让我们想到医生，城堡让我们想到战争。算法设计则要求继续抽象，直到看见变量、约束、选择与目标。
心理学叫它抽取深层结构，算法课叫它建模，禅宗大概会说：莫逐其相。
术语各有侧重，训练的核心能力却相通：从叙事中抽取可迁移的关系结构。
---
SAT——复杂度世界的世界语
走到这里，最好把四个常见名词放在桌上摆整齐。它们长得很像，职责各不相同。
- P：可以在多项式时间内求解的判定问题； - NP：给你一个多项式长度的证书后，可以在多项式时间内验证它的判定问题； - NP-hard：NP 中每个问题都能多项式归约到它； - NP-complete：既属于 NP，又是 NP-hard。
NP 的全称是 “Nondeterministic Polynomial time”。先不用被 nondeterministic 吓跑，在这篇文章里抓住 certificate 的视角就够了：
答案也许难找，但如果有人把答案拍在桌上，你能很快验货。
拿数独来说，填出完整答案可能很费力；别人递来一张填好的表，我们逐行、逐列、逐宫检查即可。那张表是 certificate，负责检查的算法是 verifier。寻找与验证之间的这道缝，正是 P vs NP 问题凝视了半个世纪的地方。
1971 年，Cook 证明 SAT 具有 NP-completeness。1972 年，Karp 又把一批经典组合问题接入归约网络。困难从此可以沿箭头传播：
图上画一根箭头很轻，真正的重量在下面四件事里：
- 实例怎么构造； - YES 如何推出 YES； - NO 如何保证仍然是 NO； - 构造为什么是多项式时间。
Cook–Levin 定理最耐人寻味的地方，是它把“存在一份可快速验证的证书”统一编码成了布尔公式。任何 NP 问题走到这里，都要学会用 SAT 的语言说话。
于是排班、路径、拼图、电路和逻辑推理，表面上各过各的日子，最后都能坐到变量与子句之间。SAT 很像复杂度世界的世界语，语法只有真假，能讲的故事却多得惊人。
---
Gadget——算法世界的机关术
从一个问题翻译到另一个问题，最棘手的部分通常是：原题的一条约束，怎样在新题里继续生效？
这时会用到 gadget。它是一小块专门设计的结构，每块负责一条局部规则：
- 变量 gadget：代表“二选一”； - 子句 gadget：代表“至少一个成立”； - 路径 gadget：代表选择顺序； - 颜色 gadget：代表互斥状态。
Gadget 有点像机关术。你无需在图旁边反复声明“这里必须二选一”，只要把两枚顶点与预算安排好，选两个的人自然会在别处付不起账。约束一旦写进结构，违规的结果可能是预算超限、某条边裸露，或路径走到半途断掉。
用制度设计的话说，它让规则自动执行；用更直白的话说：
你当然可以乱选，只是预算 k 会当场把你抓住。
下面我们来看一个经典例子。
---
从 3SAT 到 Vertex Cover——把真假装进一张图
3SAT 的输入是一个合取范式：
每个子句至多包含三个 literal。例如：
问题是：是否存在一组变量赋值，使整条公式为真？
下面的 gadget 按“每个子句恰好有三个 literal”来描述。若某个子句不足三个，可以重复其中的 literal 将它补到三个，例如 (x ∨ y) 可写成 (x ∨ y ∨ y)，可满足性不会改变。
Vertex Cover 的输入是一张无向图 G = (V, E) 和整数 k。问题是：能否选出不超过 k 个顶点，使每条边至少有一个端点被选中？
现在动手翻译。整套构造只有三种零件：变量边、子句三角形，以及连接二者的边。
1. 变量 gadget：一条必须站队的边
对于每个变量 xᵢ，建立两个顶点：
并在它们之间连边：
要覆盖这条边，至少要选一个端点。
单看这一条边，只能推出“至少选一个”。先把这个尾巴留着，稍后的预算 k 会把“至少”收紧成“恰好”。这也是归约里很常见的手法：局部 gadget 提供下界，全局预算负责卡死多余选择。
2. 子句 gadget：三角形里至少选两个
对每个三元子句建立一个三角形：
覆盖三角形的三条边至少需要两个顶点。
三角形中唯一没有被选中的那个顶点，将代表这个子句里“负责让子句成立”的 literal。
3. 接上线：让文字与图认亲
子句三角形里的每个顶点都代表一个 literal。把它连接到变量 gadget 中同名的 literal 顶点。
如果子句是：
那么三个三角形顶点就分别连接到 x₁、¬x₂、x₃。
4. 把预算锁死
若公式有 n 个变量、m 个子句，设置：
这个数并非灵光一闪，它来自每块 gadget 的最低开销：
- 每个变量 gadget 至少选 1 个，共 n 个； - 每个子句三角形至少选 2 个，共 2m 个。
预算刚好等于理论最低消费。
这意味着任何大小不超过 k 的 vertex cover 都必须：
- 在每对 xᵢ, ¬xᵢ 中恰好选一个； - 在每个子句三角形中恰好选两个。
k 在这里也是编码的一部分。它像一根刚好长度的腰带，变量 gadget 多拿一个，其他地方就扣不上了。
---
Correctness——机关搭完，开始验收
构造看起来“很有道理”还不够。归约证明最终要过 if and only if 这一关：原公式可满足时，图里确实有足够小的 vertex cover；图里出现这样的 cover 时，也必须能读回一组 satisfying assignment。
我们要证明：
（⇒）如果公式可满足，那么图有足够小的 Vertex Cover
假设已经有一组让 F 为真的赋值。
1. 对每个变量，若 xᵢ = true，就选 xᵢ 顶点；否则选 ¬xᵢ； 2. 每个子句至少有一个为真的 literal； 3. 在对应的子句三角形里，留下一个为真的 literal 顶点不选，选择另外两个顶点。
这样：
- 变量边被覆盖； - 三角形内部的边被两个已选顶点覆盖； - 未选三角形顶点连向的外部边，由那个为真的 literal 顶点覆盖； - 其余外部边由已选的三角形端点覆盖。
总共正好选择：
个顶点。
于是，每个 satisfying assignment 都对应一个大小为 n + 2m 的 vertex cover。
（⇐）如果图有足够小的 Vertex Cover，那么公式可满足
反过来，假设图存在大小不超过 n + 2m 的 vertex cover。
由于每条变量边至少要选一个端点、每个三角形至少要选两个顶点，而预算刚好只有 n + 2m，所以所有 gadget 都只能按最低消费结账：
- 每个变量对恰好选一个； - 每个子句三角形恰好选两个。
根据变量对中被选的顶点设置真假。
对任意子句，它的三角形都有一个顶点没被选。为了覆盖这个未选顶点通往变量 gadget 的外部边，对应的 literal 顶点必须被选；按我们的赋值规则，这个 literal 为真。
因此每个子句至少有一个 literal 为真，整条公式可满足。
来回都能走通，YES instance 没有在路上变质。
最后数一下零件：图中有 2n + 3m 个顶点、n + 6m 条边，构造规模为 O(n + m)。不只在多项式时间内，甚至只是线性增长。至此，这份翻译才算正式盖章。
---
证明 NP-complete——四步标准手法
考试里一看到 “prove that W is NP-complete”，可以先把纸分成两半：
左边谈验证，右边谈归约。混在一起写，很容易走着走着忘了一半。
Step 1：先处理左边，证明 W ∈ NP
说明：
- certificate 是什么； - certificate 的长度为什么是输入规模的多项式； - 如何在多项式时间内验证。
以 Vertex Cover 为例，certificate 是一组不超过 k 个顶点。Verifier 先数顶点，再扫一遍所有边，检查每条边是否至少有一个端点在集合里。Certificate 不长，检查也快，所以 Vertex Cover 属于 NP。
Step 2：给右边挑一位合适的前辈 K
这一步很看眼力。目标问题身上有什么结构，就去问题库里找同样的骨相：
- 目标问题有“选择若干元素”的味道：考虑 Vertex Cover、Independent Set、Set Cover； - 有顺序与遍历：考虑 Hamiltonian Path / Cycle； - 有精确数值：考虑 Subset Sum、Partition； - 有局部真假约束：考虑 3SAT； - 有两两兼容关系：考虑 Clique。
SAT 辈分高，不代表每次都要请祖师爷亲自出场。结构相近的源问题，会让 gadget 少很多，证明也更自然。
Step 3：构造 K ≤ₚ W
把实例映射写到别人可以照着复现：有哪些 gadget，边怎么连，参数怎样从 k 变成 k'。如果构造只能靠一句 “similarly, we build a graph”，通常说明关键部分还躲在 similarly 后面。
Step 4：证明正确性与时间复杂度
必须包含：
以及 f 可在多项式时间内计算。
收尾时把逻辑链写全：
- 因为 K 是 NP-complete 且 K ≤ₚ W，所以 W 是 NP-hard； - 又因为 W ∈ NP，所以 W 是 NP-complete。
左边和右边在这里合上：membership 管“它确实住在 NP 里”，hardness 管“NP 里的困难都能来到它门前”。两张证件齐全，才叫 NP-complete。
---
归约里的五种经典翻车
1. 箭头画反
想证明 W 很难，却写成 W ≤ₚ K。
这只能说明 W 不比已知难题 K 更难，无法证明 W 是 NP-hard。
2. 只证明 YES 会过去
你证明了：
若反方向没有证明，NO 实例仍可能被映射成 YES 实例，归约便无法保持答案。
3. 构造时偷看答案
归约函数不能调用原问题的解法，否则构造阶段已经包含了待解决的核心困难。
4. 忘记计算翻译成本
如果构造需要枚举所有解，即使映射关系正确，也不构成多项式归约。
5. 证明了 NP-hard，就顺手写 NP-complete
NP-complete 还要求问题属于 NP。
NP-hard 的范围比 NP 更广；NP-hard 问题可能是优化问题，甚至可能不可判定。证明 NP-hardness 之后，仍需单独给出多项式长度的 certificate 和多项式时间 verifier，才能得到 NP-completeness。
---
得知 NP-hard 之后还能做什么
证明写到 NP-hard，电脑并不会自动熄灭，工程也没有当场结束。我们得到的是一张路况通知：在 P ≠ NP 的通常假设下，那条“对所有输入都又快又准”的大道大概还没修出来。接下来要决定的是，绕哪条路。
1. 复用成熟求解器
现实中的排班、资源配置、验证与规划问题，经常被编码成 SAT、整数线性规划或约束满足问题，再交给高度优化的通用求解器。
这是一种工程化归约：
一旦编码完成，同一套求解器就能服务于多个领域。工程工作的重点转向建模质量、约束规模与求解器选择。
2. 传递算法
若 U ≤ₚ V，一个解决 V 的突破往往会顺着归约反向惠及 U。
归约链像学术世界的输电网：一处亮灯，沿线的问题都有可能通电。
3. 传递“不太可能”
如果已知 NP-complete 问题能归约到你的问题，那么在 P ≠ NP 的通常假设下，对所有输入都快速、精确的算法很可能不存在。
这时可以换目标：
- 做近似算法； - 做参数化算法； - 限制输入结构； - 接受指数时间但优化底数； - 使用启发式方法解决实际分布； - 用随机化、剪枝和预处理把现实实例打服。
这时理论反倒很实用。它替我们省下一段漫无目的的寻找，并逼着问题变得具体：愿意牺牲精确度，还是只处理小参数？输入是否有额外结构？最坏情况很坏，现实数据会不会温和得多？
4. 识别产生困难的约束
一个现实系统可能有几十条业务规则，而计算困难有时主要来自“整数性”“互斥选择”或“全局一致性”中的某一条。
删除它，问题可能回到 P； 保留它，指数爆炸便如影随形。
这和制度分析有些相似：流程可能长达百页，决定系统行为的关键却常常集中在少数权限与否决条件上。识别这些关键约束，有助于寻找可解的特殊情形。
---
Decision 与 Optimisation——先问能不能，再问最好有多好
复杂度理论对 YES / NO 有一种近乎执着的偏爱。原因不玄：二元答案容易搬运，也容易写出严格的“当且仅当”。
例如：
- 优化版：最短路径长度是多少？ - 判定版：是否存在长度不超过 L 的路径？
有优化算法时，判定很轻松：先求最优值，再和 L 比较。
手里只有判定算法也未必吃亏。当目标值具有单调性，可以对 L 做二分搜索，用若干次 YES / NO 逐步逼近最优值。
于是“能不能”和“最好有多好”之间，经常只隔着一个阈值与一次搜索。论文先研究判定版，未必是对现实目标失去兴趣；只是 YES / NO 更适合搭桥。
语言越小，证明越硬。
---
总结——All problems wear masks.
如果只带走几样东西，我希望是下面这些。
1. U ≤ₚ V 是一条可执行的翻译路线。U 的实例沿 f 走到 V，答案原样抵达，路费控制在多项式时间内。
2. 箭头指向承担困难的一方。想证明新问题 W 是 NP-hard，就把一个已知 NP-complete 问题送进 W。这条规则值得在草稿纸顶端写一遍，能救很多证明。
3. Gadget 的精妙处不只在“画出一个像变量的结构”。更关键的是让预算、边和局部选择互相咬合，最后逼出恰好对应的逻辑。好的 gadget 像榫卯，单看每一块都不复杂，拼起来却不允许你随便动。
4. 归约训练的是一种看穿表述的能力。攻城与放射治疗相隔甚远，抽掉故事以后，都可以剩下“分散安全通过，再同时汇聚”。算法题也常这样：先别急着搜代码模板，看看眼前的对象、关系、约束和目标，是否早已在另一道题里见过。
5. NP-hard 是方向提示。它会把精力引向更诚实的问题：近似到什么程度？哪个参数很小？哪些输入有特殊结构？现实数据是否允许启发式方法跑得很好？承认边界以后，路反而多了。
世界喜欢给同一个问题换无数张面具。
有人看见医疗、物流、社交、旅行与电路； 有人看见变量、约束、证书与图。
归约在这些表象之间搭桥。桥需要经得起三次检查：怎么造，真假有没有变，走过去要多久。
桥这边的问题说：
我不知道自己该怎么解决。
桥那边的问题回答：
没关系，我认得你的骨头。
Reduce it, my friend.
---
References
- Stephen A. Cook, The Complexity of Theorem-Proving Procedures, 1971. - Richard M. Karp, Reducibility Among Combinatorial Problems, 1972. - Mary L. Gick & Keith J. Holyoak, Analogical Problem Solving90013-4), 1980. - NASA Science, What Is the Universe?. - COMP3121/9101 course material: Module 4 — Intractable Problems, Course Notes, and Some Useful NP-hard Problems.