第6章：时间复杂性（Time Complexity）

一、导读

1.1 本章学习目标

第6章是计算复杂性理论的核心——P 与 NP 问题。这是计算机科学中最重要的未解问题之一。

1.2 为什么第六章如此重要

P vs NP 问题定义了计算的效率边界。理解 P、NP 和 NP 完全性，是理解算法复杂性的关键。

1.3 核心问题引导

P 类和 NP 类有什么区别？

什么是 NP 完全性？

Cook-Levin 定理是什么？

P vs NP 问题为什么重要？

二、核心概念详解

6.1 P 类

P（Polynomial time）：可以在多项式时间内被图灵机判定的语言。

P 中的问题：
- 排序：O(n log n)
- 最短路径：O(n²)
- 矩阵乘法：O(n³)
- 2-SAT：O(n)

P 被认为是"可有效解决的"问题

6.2 NP 类

NP（Nondeterministic Polynomial time）：可以在多项式时间内被非确定性图灵机判定的语言。等价地，可以在多项式时间内被验证的语言。

NP 中的问题：
- SAT（布尔可满足性）
- 旅行商问题（TSP）
- 图着色问题
- 子集和问题

NP 中的问题可以在多项式时间内验证解
但可能无法在多项式时间内找到解

6.3 NP 完全性

语言 $L$ 是 NP 完全的，如果：

$L \in NP$

对于所有 $A \in NP$，$A \leq_p L$（多项式时间可归约）

NP 完全问题的特点：
- 如果任何一个 NP 完全问题有多项式时间算法
- 则所有 NP 问题都有多项式时间算法
- 即 P = NP

已知的 NP 完全问题：
- SAT（第一个被证明的 NP 完全问题）
- 3-SAT
- CLIQUE
- VERTEX-COVER
- TSP（判定版）
- SUBSET-SUM

6.4 Cook-Levin 定理

定理：SAT 是 NP 完全的。

这是计算复杂性理论中最重要的定理之一。它证明了 SAT 是第一个 NP 完全问题，为后续所有 NP 完全性证明奠定了基础。

6.5 P vs NP

三种可能：
1. P = NP：所有可验证的问题都可高效解决
   → 密码学崩溃，优化问题迎刃而解
2. P ≠ NP：存在可验证但不可高效解决的问题
   → 大多数科学家相信这个
3. 不可证明：P vs NP 独立于现有公理系统

三、实战案例

6.1 证明 NP 完全性

证明新问题是 NP 完全的步骤：
1. 证明问题在 NP 中（可以在多项式时间验证解）
2. 选择一个已知的 NP 完全问题
3. 构造从已知问题到新问题的多项式时间归约

示例：证明 3-SAT 是 NP 完全的
- 3-SAT ∈ NP（容易验证）
- SAT ≤_p 3-SAT（将一般 SAT 转换为 3-SAT）
- 因此 3-SAT 是 NP 完全的

四、本章小结

P vs NP 是计算机科学最重要的未解问题。P 是可有效解决的问题，NP 是可验证的问题。NP 完全问题是 NP 中最难的问题，如果任何一个有多项式算法，则 P = NP。

五、思考与练习

P vs NP 为什么重要？

如何证明一个问题是 NP 完全的？

Cook-Levin 定理的意义是什么？

如果 P = NP 会发生什么？

实际中如何处理 NP 完全问题？