8.5 经典归约链——从SAT到图问题

问题：SAT、顶点覆盖、团问题有什么共同点？如何从一个归约到另一个？

---

归约链全景

从Cook定理出发，我们可以建立一系列经典归约：

Cook定理      多项式变换       器件构造      补图变换     距离设计
────────     ───────────     ──────────    ─────────    ─────────

任意NP ─────→ SAT ─────→ 3-SAT ─────→ VC ─────→ CLIQUE ─────→ TSP

这条链的意义：

• 每个箭头表示一个归约
• 每个归约证明了目标问题的NP完全性
• 归约链展示了问题的内在联系

让我们逐个学习这些归约的器件构造。

---

归约1：SAT → 3-SAT

问题

SAT子句长度任意，3-SAT每子句恰好3文字。

需要把任意长度子句转换为恰好3文字子句。

归约方法

长子句（>3文字）

例子：(x₁ ∨ x₂ ∨ x₃ ∨ x₄)

转换：

(x₁ ∨ x₂ ∨ y₁) ∧ (¬y₁ ∨ x₃ ∨ y₂) ∧ (¬y₂ ∨ x₄ ∨ True)

其中y₁, y₂是辅助变量，True是任意真值（如z ∨ ¬z）。

短子句（<3文字）

例子：(x₁ ∨ x₂)

转换：

(x₁ ∨ x₂ ∨ z) ∧ (x₁ ∨ x₂ ∨ ¬z)

其中z是新变量。两个子句必须同时满足，z为真或假不影响结果。

为什么等价？

长子句分析：

原：(x₁ ∨ x₂ ∨ x₃ ∨ x₄) 可满足 ⟺ 至少一个为True

转换后：

• 如果x₁或x₂为True，选y₁=True，(x₁∨x₂∨y₁)满足
• 如果x₃为True，选y₁=False, y₂=True
• 如果x₄为True，选y₁=False, y₂=False
• (¬y₂∨x₄∨True)总是满足

关键：辅助变量的存在不改变可满足性。

短子句分析：

(x₁ ∨ x₂) 可满足 ⟺ (x₁∨x₂∨z)∧(x₁∨x₂∨¬z) 可满足

因为：

• 如果x₁∨x₂为True，两个子句都满足
• 如果x₁∨x₂为False，则需要z=True和z=False同时成立，不可能

归约复杂度

• 每个子句：最多O(k)个新子句（k是原子句长度）
• 新变量：最多O(总文字数)个
• 归约时间：多项式时间

---

归约2：3-SAT → Vertex Cover

这是最经典的归约之一，展示了器件构造的艺术。

问题

3-SAT：布尔公式，每子句恰好3文字，判断是否可满足。

Vertex Cover：给定图G和整数k，判断是否存在大小≤k的顶点覆盖。

归约构造

给定3-SAT实例：n个变量，c个子句。

构造图G：

• 顶点数：2n + 3c
• 边数：n + 3c（变量器件边）+ 3c（子句器件三角形内部）+ 连接边

变量器件

对每个变量x：

• 创建两个顶点：x和¬x
• 连一条边：(x, ¬x)

    x ─────── ¬x

意义：

• 覆盖这条边必须选x或¬x
• = 必须赋x为True或False
• 强制二选一！

子句器件

对每个子句(x ∨ y ∨ z)：

• 创建三角形：三个顶点对应三个文字

        ○ (x)
       / \
      ○──○
    (z) (y)

意义：

• 覆盖三角形需要选至少2个顶点（三角形3条边）
• 第3个顶点必须通过其他方式覆盖

连接设计

子句器件的每个顶点，连接到对应的变量器件顶点：

    x ─────── ¬x        (变量器件)
     │         │
     ○──○──○              (子句器件)

例如，子句(x∨y∨z)中的"文字x"顶点，连接到变量器件的x顶点。

覆盖大小目标

设k = n + 2c

为什么是n+2c？

• n个变量器件边：需要n个顶点覆盖
• c个子句器件三角形：需要至少2c个顶点覆盖（每个三角形选2个）
• 总共：n + 2c

等价性论证

正向：3-SAT可满足 → 存在覆盖

假设3-SAT可满足，赋值为φ。

构造覆盖C：

1. 变量器件：对于每个变量x

   • 如果φ(x)=True，选x顶点
   • 如果φ(x)=False，选¬x顶点
   • 共n个顶点

2. 子句器件：对于每个子句(x∨y∨z)

   • 至少一个文字为真，假设是x
   • 在三角形中选y和z顶点（不选x）
   • x顶点已被变量器件选中（连接到变量器件的x）
   • 共2c个顶点（每个子句选2个）

3. 验证覆盖：

   • 变量器件边：被选中顶点覆盖
   • 子句器件三角形：被选中的2个顶点覆盖
   • 连接边：如果选了"文字x"顶点在变量器件，则"子句器件x"顶点到"变量器件x"的边被覆盖
   • 如果在子句器件选了某个顶点，则其连接边也被覆盖

总覆盖大小：n + 2c

反向：存在覆盖 → 3-SAT可满足

假设存在大小为n+2c的覆盖C。

提取赋值φ：

1. 变量器件：

   • 每条变量器件边必须被覆盖
   • 只能选x或¬x之一（否则超过n个）
   • 赋值：选x → φ(x)=True，选¬x → φ(x)=False

2. 子句器件：

   • 每个三角形需要至少2个顶点覆盖（三角形有3条边）
   • 如果选3个顶点，总覆盖超过n+2c（因为每个子句至少贡献2个，共2c+n，选3个会超标）
   • 所以每个三角形恰好选2个顶点
   • 第3个顶点未被选中，必须通过连接边被覆盖
   • = 连接的变量器件顶点被选中
   • = 该文字为真

3. 验证满足：

   • 每个子句的第3个顶点（未选）连接到满足的文字
   • = 每个子句至少一个文字为真
   • = 3-SAT可满足

归约复杂度

• 创建顶点：O(n + c)
• 创建边：O(n + c + 连接数) = O(n + c)
• 归约时间：多项式时间

---

归约3：Vertex Cover → CLIQUE

问题

Vertex Cover：找覆盖所有边的顶点集合。

CLIQUE：找完全子图（所有顶点互相连接）。

关键定理

定理：S是G的顶点覆盖 ⟺ V\S是G的补图中的团。

其中G的补图G'：边(u,v)在G中 ⟺ 边(u,v)不在G'中。

直觉理解

Vertex Cover视角：

• 选一些顶点覆盖所有边
• 未选的顶点之间没有边（否则那条边未被覆盖）

CLIQUE视角：

• 未选的顶点之间没有边（在G中）
• = 未选的顶点之间有所有边（在G'中）
• = 未选的顶点在G'中形成完全子图
• = 未选的顶点在G'中形成团

归约构造

给定Vertex Cover实例(G, k)：

构造CLIQUE实例(G', |V| - k)：

1. G' = G的补图：所有G中没有的边，在G'中都有
2. 目标团大小 = |V| - k

等价性论证

正向：G有大小为k的覆盖S ⟺ G'有大小为|V|-k的团V\S

• S覆盖G的所有边 ⟺ V\S中没有G的边
• V\S中没有G的边 ⟺ V\S中有G'的所有边
• V\S中有G'的所有边 ⟺ V\S是G'的团

反向：G'有大小为|V|-k的团C ⟺ G有大小为k的覆盖V\C

• C是G'的团 ⟺ C中有G'的所有边
• C中有G'的所有边 ⟺ C中没有G的边
• C中没有G的边 ⟺ V\C覆盖G的所有边

归约复杂度

• 创建补图：O(|V|²)（检查所有可能的边）
• 归约时间：多项式时间

---

归约4：CLIQUE → TSP

问题

CLIQUE：找大小为k的团（完全子图）。

TSP：找经过所有城市的最短路线。

这里我们用TSP的判定版本：是否存在长度≤K的路线？

归约构造

给定CLIQUE实例(G, k)：

构造TSP实例：

1. 城市：图的每个顶点 + 一个额外城市
2. 距离矩阵：
   • 相邻顶点距离 = 1
   • 不相邻顶点距离 = 2
   • 额外城市到所有顶点距离 = 1
3. 目标长度：K = k（只经过团中的顶点）

注意：这里TSP的判定版本是"是否存在长度为k的路线"，不是传统TSP。

等价性论证

正向：G有大小为k的团C ⟺ TSP存在长度为k的路线

• 如果存在k团，只经过团中的顶点
• 团中顶点互相连接，距离都是1
• 路线长度 = k

反向：TSP存在长度为k的路线 ⟺ G有大小为k的团

• 如果路线长度为k，所有相邻顶点距离必须为1
• = 所有相邻顶点必须在G中相邻
• = 这些顶点形成团

---

归约链的意义

为什么建立归约链？

1. 证明NP完全性：每个归约证明目标问题的NP完全性
2. 揭示内在联系：不同问题有相同的"难度内核"
3. 归约工具库：学习器件构造，为证明新问题NP完全做准备

归约器件总结

归约	核心器件	关键洞察
SAT → 3-SAT	辅助变量分组	限制子句长度不改变可满足性
3-SAT → VC	变量器件+子句器件	布尔选择 → 图选择
VC → CLIQUE	补图变换	覆盖 = 补图的团
CLIQUE → TSP	距离矩阵设计	连接性 → 路径长度

---

练习

基础练习

1. 归约理解

   解释每个归约的核心器件：

   • 3-SAT → VC的变量器件为什么这样设计？
   • VC → CLIQUE为什么用补图？

2. 器件可视化

   给定3-SAT实例：(x∨y∨¬z)∧(¬x∨y∨z)∧(x∨¬y∨z)

画出对应的Vertex Cover器件图（变量器件和子句器件）。

进阶练习

3. 归约实现

   实现SAT → 3-SAT的归约算法：

   def sat_to_3sat(formula):
       """
       输入：SAT实例（列表的列表，每个子句是文字列表）
       输出：3-SAT实例
       """
       pass

4. 反向归约

   设计CLIQUE → Vertex Cover的归约。

   这与VC → CLIQUE有什么关系？

5. 等价性验证

   对于练习2中构造的图，设覆盖大小k = n + 2c = 3 + 6 = 9。

   给出一个可满足赋值，并构造对应的覆盖。

   给出一个大小为9的覆盖，并提取对应的赋值。

思考题

6. 器件设计原则

   回顾Skiena六法则，分析这些归约如何应用法则：

   • 法则1（源问题受限）：体现在哪里？
   • 法则4（惩罚不良选择）：体现在哪里？

---

小结

归约	核心器件	等价性关键
SAT → 3-SAT	辅助变量分组	不改变可满足性
3-SAT → VC	变量器件边 + 子句器件三角形	覆盖大小 = n + 2c
VC → CLIQUE	补图变换	覆盖 = 补图的团
CLIQUE → TSP	距离矩阵（相邻=1，不相邻=2）	团 → 路径长度k

核心洞见：归约链展示了NP完全问题的内在联系。SAT、顶点覆盖、团问题、TSP看似不同，但它们的"难度内核"相同——都是选择+约束的组合问题。

---

下一节：我们将学习如何识别和证明新问题的NP完全性。