算法分析与设计

Appearance

8.3 NP完全性与Cook定理——问题的等价性 ​

问题：是否存在一个"最难"的NP问题？如果解开了它，所有NP问题都能解决？

一个惊人的发现 ​

1971年，Stephen Cook证明了一个令人震惊的定理：SAT问题是NP完全的。

这意味着：

  • SAT在NP中（可验证）
  • 所有NP问题都能在多项式时间内转换为SAT
  • 如果SAT有多项式时间算法，则P=NP

换句话说，SAT是NP问题的"通用语言"——解开了SAT，就解开了所有NP问题。

NP完全性的定义 ​

NP-hard（NP难） ​

定义：问题H是NP-hard，如果所有NP问题都能在多项式时间内归约到H。

L ≤ₚ H 对所有L ∈ NP

其中≤ₚ表示多项式时间归约。

直觉：NP-hard问题"至少和NP中任何问题一样难"。

NP-complete（NP完全） ​

定义：问题C是NP-complete，如果：

  1. C在NP中
  2. C是NP-hard

直觉：NP-complete问题是"NP中最难的问题"。

关键定理 ​

定理：如果任何一个NP-complete问题在P中，则P=NP。

证明：

  1. 设C是NP-complete且C ∈ P
  2. 对于任意L ∈ NP，L ≤ₚ C（因为C是NP-hard）
  3. 因为C ∈ P，所以L ∈ P（多项式时间的多项式还是多项式）
  4. 因此NP ⊆ P
  5. 又P ⊆ NP
  6. 所以P=NP

意义：只要找到一个NP-complete问题的多项式算法，就解决了P=NP问题。

Cook定理：SAT是NP完全的 ​

SAT问题 ​

布尔可满足性问题（SAT）：给定布尔公式（合取范式），判断是否存在变量赋值使公式为真。

合取范式（CNF）：

  • 文字：变量或变量的否定（x 或 ¬x）
  • 子句：文字的析取（x₁ ∨ ¬x₂ ∨ x₃）
  • 公式：子句的合取（子句₁ ∧ 子句₂ ∧ ...）

例子：(x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ x₃) ∧ (x₂ ∨ x₃)

存在赋值使公式为真吗？是的，x₁=True, x₂=False, x₃=True。

Cook定理陈述 ​

定理（Cook, 1971）：SAT是NP完全的。

证明思路 ​

证明分两步：

第一步：SAT在NP中 ​

  • 证书：变量赋值
  • 验证器：代入赋值，计算公式真值
  • 验证时间：O(子句数 × 变量数) = 多项式时间

因此SAT ∈ NP。

第二步：所有NP问题都能归约到SAT ​

这是证明的核心。思路如下：

  1. NP问题的本质

    NP问题 = 存在多项式时间验证器V(x, c)

    验证器是一个确定性图灵机，在多项式时间p(|x|)内运行。

  2. 图灵机计算的布尔编码

    图灵机的计算过程可以用布尔变量表示：

    • Q[i,t]：时刻t，状态为i
    • H[j,t]：时刻t，读写头在格子j
    • S[j,a,t]：时刻t，格子j包含符号a

  3. 转移规则的布尔约束

    图灵机的每条转移规则可以编码为布尔子句：

    • "如果在状态q读取a，则转移到状态q'，写入a'，移动方向d"
    • 转化为：(Q[q,t] ∧ H[j,t] ∧ S[j,a,t]) → (Q[q',t+1] ∧ ...)

  4. 构造SAT实例

    给定NP问题实例x，构造SAT公式：

    • 变量：图灵机在时刻0到p(|x|)的状态、位置、带内容
    • 子句：确保转移正确、初始配置正确、最终接受

  5. 等价性

    • SAT可满足 ⟺ 存在证书c使V(x, c)接受
    • 因为SAT编码了"是否存在有效计算路径"

为什么SAT是"通用语言"？ ​

任何计算都可以表达为布尔约束：

  • 图灵机的每一步转移都是布尔操作
  • 图灵机的整个计算过程是布尔公式的合取
  • SAT可以"模拟"任何图灵机

直觉：SAT就像乐高积木——用简单的布尔逻辑，可以搭建任何计算。

3-SAT：更标准的NP完全问题 ​

虽然SAT是第一个被证明的NP完全问题，但在实际归约中，我们更常用3-SAT。

3-SAT问题 ​

定义：SAT的特例，每个子句恰好有3个文字。

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

SAT ≤ₚ 3-SAT ​

定理：3-SAT是NP完全的。

证明思路：

  1. 3-SAT在NP中（显然，是SAT的特例）
  2. SAT ≤ₚ 3-SAT（需要构造归约）

归约构造 ​

长子句 → 多个3-文字子句：

子句 (x₁ ∨ x₂ ∨ x₃ ∨ x₄) 转化为：

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

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

短子句 → 多个3-文字子句：

子句 (x₁ ∨ x₂) 转化为：

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

关键性质：辅助变量不改变可满足性。

NP完全性的意义 ​

为什么NP完全性重要？ ​

  1. 统一视角：所有NP完全问题"等价"——解开一个，解开全部

  2. 识别困难：如果问题是NP完全的，可能需要接受近似解

  3. 理论基准：NP完全问题是计算复杂性的基准点

NP完全问题族谱 ​

从Cook定理出发，我们可以证明更多问题的NP完全性：

        Cook定理
           ↓
          SAT
           ↓
        3-SAT ←────────────────┐
           ↓                    │
     Vertex Cover               │
      ↓       ↓                 │
    Clique   Hamiltonian Path   │
      ↓                          │
     TSP ←───────────────────────┘

每个箭头表示一个归约。如果A → B，则B至少和A一样难。

LLM关联：Prompt约束满足 ​

SAT问题与LLM有什么关系？

Prompt约束 ​

当你写Prompt时：

请写一篇文章：
1. 字数在500-800字之间
2. 包含"创新"这个词
3. 不包含"技术"这个词
4. 第一段要有疑问句
5. 最后一段要有总结

这本质上是一个约束满足问题，类似于SAT：

  • 变量：每个词的选择
  • 约束：各种要求
  • 目标：满足所有约束

为什么复杂Prompt容易失败？ ​

如果约束太多、太复杂，问题变得像SAT：

  • 约束之间可能冲突
  • 验证容易（检查是否满足），但生成困难
  • LLM可能在指数级搜索空间中挣扎

启示 ​

理解SAT的NP完全性，有助于理解：

  • 为什么简单Prompt效果好
  • 为什么复杂约束需要迭代优化
  • 为什么"生成+验证"架构有效

练习 ​

基础练习 ​

  1. 理解NP完全性

    为什么NP-complete问题被称为"NP中最难的问题"？ 如果一个NP-complete问题在P中，为什么P=NP？

  2. SAT验证器

    实现一个SAT验证器，给定布尔公式和赋值，判断公式是否可满足。

    python
    # 输入格式
formula = [
    [('x1', False), ('x2', True)],   # (x1 ∨ ¬x2)
    [('x1', True), ('x3', False)]    # (¬x1 ∨ x3)
]
assignment = {'x1': True, 'x2': False, 'x3': True}

进阶练习 ​

  1. 3-SAT转化

    将以下SAT实例转化为3-SAT：

    • (x₁ ∨ x₂ ∨ x₃ ∨ x₄ ∨ x₅)
    • (x₁ ∨ x₂)

    证明转化前后可满足性等价。

  2. Cook定理直觉

    用自己的话解释Cook定理的直觉：为什么SAT可以"模拟"任何图灵机？

思考题 ​

  1. NP-hard vs NP-complete

    NP-hard和NP-complete有什么区别？ 给出一个NP-hard但不是NP-complete的问题例子。

  2. Prompt设计

    你认为什么样的Prompt约束会让问题变得更像SAT？ 如何设计Prompt使约束更容易满足？

小结 ​

概念要点
NP-hard所有NP问题可归约到它，不一定在NP中
NP-completeNP-hard且在NP中，NP中最难的问题
Cook定理SAT是NP完全的，是NP问题的"通用语言"
3-SATSAT的标准化形式，每子句恰好3文字
归约链SAT → 3-SAT → Vertex Cover → ...

核心洞见：NP完全性揭示了问题的等价性——解开了SAT，就解开了所有NP问题。这正是NP完全性理论的核心价值。

下一节：我们将学习归约的具体方法——如何把一个问题"翻译"成另一个问题。

新时代的算法课程