# 第九章 NP完全性 (NP-Completeness)

### 一、 9.1 判定问题

本节探讨了什么是“好算法”、问题与算法的复杂性，以及为什么要将优化问题转化为判定问题。

#### 1. 什么是好算法？

* **评价标准**：运行时间是评价算法好坏的重要标准。


* **衡量维度**：通常考虑解决规模为 $n$ 的问题需要的计算时间，或者单位时间内能够解决的问题规模 $n$。


* **典型算法对比**：PPT中对比了三个经典的算法：


* **快速排序算法**：复杂度为 $O(n \log n)$，解决的是排序问题。


* **Dijkstra算法**：复杂度为 $O(n^2)$，解决的是图的单源最短路径问题。


* **最大团问题的回溯法**：复杂度为 $O(n 2^n)$，解决的是求最大完全子图问题。





#### 2. 问题规模与计算时间的具体量化（假设使用每秒执行 $10^9$ 次的超大型计算机）

* **快速排序算法 ($O(n \log n)$)**：在问题规模为 $10^5$ 个数据时，运算量约为 $10^5 \times \log_2 10^5 \approx 1.7 \times 10^6$ 次，计算时间仅需约 $1.7 \times 10^{-3}$ 秒。


* **Dijkstra算法 ($O(n^2)$)**：在问题规模为 $10^4$ 个顶点时，运算量为 $(10^4)^2 = 10^8$ 次，计算时间需要 0.1 秒。


* **最大团问题的回溯法 ($O(n 2^n)$)**：在问题规模仅为 $10^2$（100个顶点）时，运算量高达 $100 \times 2^{100} \approx 1.8 \times 10^{32}$ 次，计算时间需要惊人的 $5.7 \times 10^{15}$ 年。



#### 3. 单位时间能够解决的问题规模（增大计算机运算能力至每秒 $6 \times 10^{10}$ 次）

* **快速排序算法**：1 秒钟可以处理 $2 \times 10^9$（即 20 亿）个数据的排序。


* **Dijkstra算法**：1 秒钟可以处理具有 $2.4 \times 10^5$ 个顶点的图。


* **最大团问题的回溯法**：给它整整**一天**的时间，也只能解决 41 个顶点的图。


* **结论**：快速排序和 Dijkstra 算法能快速解决大问题，是**好算法**。而最大团的回溯法只能用于极小的图，稍大一点（如100个顶点）在现实中就根本不可行。



#### 4. 多项式时间算法 vs 非多项式时间算法

* **多项式时间算法（好算法）**：其复杂度随着规模增长较慢，关系为 $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3)$。


* **非多项式时间算法（指数级/坏算法）**：其复杂度随规模暴增，关系为 $O(2^n) < O(n!) < O(n^n)$。



#### 5. 算法复杂性 vs 问题复杂性

* **算法的复杂性**：指解决问题的某一个**具体算法**的执行时间，是算法本身的性质。


* **问题的复杂性**：指**这个问题本身**的内在困难程度，是问题的性质。


* **以排序问题为例**：冒泡排序是 $O(n^2)$，快速排序平均是 $O(n \log n)$，而排序问题本身的复杂性是 $O(n \log n)$。因为问题的复杂性定义为**所有能解决该问题的算法中，最好的那个算法的复杂性**。



#### 6. 现实世界问题的分类

* **多项式级问题**：已经设计出多项式级算法的问题（如排序、最小生成树、单源最短路径）。


* **不满足计算性的问题**：根本不存在任何求解算法的问题（如希尔伯特第十问题）。


* **指数级的问题**：已设计出指数算法，且**已证明绝不存在**多项式级算法的问题（如带幂运算的正则表达式的全体性）。


* **尚不确定多项式级的问题**：已设计出指数级算法，但**目前既不能证明它存在、也不能证明它不存在**多项式算法（许多优化问题属于此类，如图着色、货郎担/TSP、0/1背包问题）。



#### 7. 优化问题转化为判定问题

* **判定问题**：是指只需要回答“是（Yes）”或“否（No）”的问题。


* **转化示例**：
* **图着色问题**：优化问题是“求最少需要多少种颜色”；转化后的判定问题是“问该图是否可以用 $m$ 种颜色进行着色？”


* **最大团问题**：优化问题是“求图 $G$ 内的最大完全子图（团）和它的大小”；判定问题是“问图 $G$ 是否存在一个大小为 $k$ 的团？”


* **0/1背包问题**：优化问题是“限定容量 $M$ 下如何选择物品使效益最大”；判定问题是“给定效益值 $X$，是否存在一组策略使总效益 $\ge X$？”




* **相互转化的方法（以最大团为例）**：
* **判定 $\rightarrow$ 优化**：假设判定算法为 `DCLIQUE(G,k)`，我们只需要让 $k$ 从顶点总数 $n$ 开始，依次检验 $n, n-1, n-2 \dots$，直到算法首次输出 1（是），此时的 $k$ 就是最大团大小。若判定算法耗时 $f(n)$，则优化问题可在 $n \times f(n)$ 时间内求出。


* **优化 $\rightarrow$ 判定**：直接求解优化问题得到最大团大小 $j$，如果 $j < k$ 则判定返回否，否则返回是。若优化算法耗时 $g(n)$，判定也可在 $g(n)$ 内完成。


* **核心结论**：最大团问题与其判定问题**可以在多项式时间内相互转换**。




* **转化的好处**：消除了不同优化问题纷繁复杂的输出差异，将所有输出统一成了简洁的“是”与“否”。如果判定问题在多项式时间内不可解，那么对应的优化问题也绝对无法在多项式时间内求解。



---

### 二、 9.2 不确定的判定问题

本节引入了一个虚拟的理论模型——**不确定算法**与**不确定机**，用于分析那些极难问题的复杂性。

#### 1. 不确定算法与描述语句

* **概念**：取消运算的“确定性”限制，允许运算结果受限于某个特定的集合。


* **SPARKS语言中的三个核心新函数/语句**（它们的时间复杂度在理论上恒为 $O(1)$）：
* `choice(S)`：按照题意直接选取集合 $S$ 中的一个元素。


* `failure`：发出不成功完成的信号。


* `success`：发出成功完成的信号。




* **检索问题的不确定算法示例**：
在集合 $A(1:n)$ 中找 $X$ 的下标 $j$，找不到则 $j=0$。


```pascal
j <- choice(1:n)
if A(j) = X then success endif
j <- 0; failure

```

  该不确定算法的复杂度仅为 $O(1)$。

#### 2. 不确定算法的确定解释与不确定机
* **并行的确切解释**：可以理解为每当遇到 `choice` 选择时，算法就会自我复制出若干副本同时执行，第一个成功的副本会终止其他副本；失败的副本只终止自己（这只是为了便于人类理解）。
* **不确定机（上帝视角）**：这是一个虚构的、拥有“魔力”的理论模型。它在执行算法时没有副本，但总能在 $O(1)$ 时间内“直接猜中”正确的解。如果问题有解，它直接返回需要的元素；如果无解，它随机返回一个。在现实技术下它并不存在。

#### 3. 不确定算法的设计步骤与复杂度计算
* **第一阶段：猜想阶段（不确定阶段）**：利用 `choice` 语句“猜”出一个候选解。
* **第二阶段：验证阶段（确定阶段）**：用确定性的逻辑验证这个猜出来的解是否真的是答案。
* **多项式时间可验证**：如果一个不确定算法的**验证阶段**的时间复杂度是多项式级的，就称其为多项式时间可验证。
* **时间复杂度定义**：若返回 `failure`，我们不关注，认为恒为 $O(1)$；若返回 `success`，则算法总复杂度 = 不确定阶段复杂度 + 确定阶段复杂度。

#### 4. 排序问题的不确定算法 (NSORT)
* **思想**：用辅助数组 $B$ 保存结果。
* **代码逻辑**：
```pascal
  // 构造/猜想阶段：复杂度 O(n)
  for i <- 1 to n do
      j <- choice(1:n); if B(j) != 0 then failure endif
      B(j) <- A(i)
  repeat
  // 验证阶段：复杂度 O(n)
  for i <- 1 to n-1 do
      if B(i) > B(i+1) then failure endif
  repeat
  print(B); success

```


* **总结**：总复杂度为 $O(n) + O(n) = O(n)$。



#### 5. 最大团判定问题的不确定算法 (DCK)

* **代码逻辑**：
```pascal
// 不确定阶段：从 n 个点中猜出 k 个点放入集合 S，复杂度 O(k)
for i <- 1 to k do
    t <- choice(1:n); if t ∈ S then failure endif
    S <- S ∪ {t}
repeat
// 确定验证阶段：验证 S 中的任意两点之间是否都有边连接，复杂度 O(k²)
for 每一对 i, j ∈ S 且 i != j do
    if (i, j) 不是此图的边 then failure endif
repeat
success

```

* **总结**：总复杂度为 $O(k + k^2) = O(n^2)$。

#### 6. 问题规模的二进制表示
* 为了统一量化不同判定问题的算法复杂度，所有输入参数都必须转换成二进制形式，复杂度基于**二进制输入的长度**来考虑。
* **最大团算法 DCK 的二进制长度 $m$ 破析**：
  * 图 $G$ 由二进制邻接矩阵表示，占用 $n^2$ 位。
  * 判定值 $k$ 占用 $\lfloor \log_2 k \rfloor$ 位。
  * 顶点数 $n$ 占用 $\lfloor \log_2 n \rfloor$ 位。
  * 总输入长度 $m = n^2 + \lfloor \log_2 k \rfloor + \lfloor \log_2 n \rfloor + 2$。
  * 因此，DCK 的复杂度 $O(n^2) = O(m)$，在二进制输入度量下是多项式时间的。

---

### 三、 9.3 NP问题与NP完全性

这一节进入了本章的核心：定义 P 与 NP，引入“归约”的概念，并详细推导几个著名的 NP-完全问题。

#### 1. P 问题与 NP 问题的定义
* **P 问题 (Polynomial)**：所有可以在多项式时间内用**确定算法**求解的判定问题的集合。
* **NP 问题 (Nondeterministic Polynomial)**：所有可以在多项式时间内用**不确定算法**求解（即：能在多项式时间内猜出一个解并验证一个解）的判定问题的集合。
* **包含关系**：P 问题是 NP 问题的一种特例（即 `choice(S)` 集合中只有唯一一个元素时），因此 **$P \subseteq NP$ 恒成立**。
* **现状**：目前科学界尚不确定 $P=NP$ 还是 $P \neq NP$。

#### 2. NP-完全理论 (NPC) 的基本思想
* **定义**：NP-完全问题是 NP 类问题中极其特殊的一类，它满足：
  * 如果其中任何**一个**问题找到了多项式时间算法，那么**所有**的 NP 问题都能在多项式时间内解决（即 $P=NP$）。
  * 反之，若能证明其中任何一个问题是多项式时间不可解的，则所有的 NP 问题都不可解。
* **历史奠基**：1971年 S. Cook 发表了著名论文奠定了基础；1972年 R. Karp 发表论文进一步完善。

#### 3. 归约 (Reduction) 的定义
* **概念**：用归约来表达不同问题的相对难度关系。
* **符号表示**：$L_1 \le L_2$ 或 $L_1 \propto L_2$。
* **机制**：如果存在一个转换函数 $T(x)$，能将问题 $L_1$ 的任意合法输入 $x$，转换成问题 $L_2$ 的合法输入 $T(x)$。并且满足：$L_1$ 对输入 $x$ 的输出是 yes，当且仅当 $L_2$ 对输入 $T(x)$ 的输出是 yes。
* **直观意义**：若 $L_1 \le L_2$，说明 $L_2$ 的时间复杂度不低于 $L_1$，即 **$L_1$ 不比 $L_2$ 难**。同时，归约具有**传递性**。
* **布尔值归约到整数的例子**：
  * $L_1$：判定 $n$ 个布尔值中是否至少有一个为 true。
  * $L_2$：判定 $n$ 个整数中的最大元素是否为正数。
  * 转换函数 $T$：若 $X_i = \text{true}$ 则对应的 $Y_i = 1$；若 $X_i = \text{false}$ 则 $Y_i = 0$。通过这样多项式的转换，就把 $L_1$ 成功归约到了 $L_2$。

#### 4. 多项式时间归约
* **定义**：如果计算转换函数 $T$ 的算法本身是多项式级的，则称 $L_1$ 可以多项式时间归约到 $L_2$，记为 $L_1 \le_p L_2$。
* **重要性质**：若 $L_1 \le_p L_2$：
  * 如果 $L_2$ 是多项式级可解决的，那么 $L_1$ 也是。
  * 如果 $L_2$ 是指数级才能解决的，那么 $L_1$ 也是。

#### 5. NP-完全问题 (NPC) vs NP-难问题 (NP-hard)
* **NP-完全问题 (NPC)** 必须同时满足：
  1. $L \in NP$。
  2. 对于每一个 $L' \in NP$，都有 $L' \le_p L$。
* **NP-难问题 (NP-hard)** 只需要满足：
  1. 对于每一个 $L' \in NP$，都有 $L' \le_p L$。
* **区别**：NP-难问题**不一定**属于 NP 问题，它的范围比 NP-完全更广，它有可能比所有的 NP-完全问题还要难，更不可能找到多项式算法。
* **关系图解**：
  * 若 $P \neq NP$：P 和 NPC 是 NP 的两端，NP-Hard 在上方覆盖了 NPC 并延伸到 NP 之外。
  * 若 $P = NP$：则 $P = NP = NPC$，而 NP-Hard 依然有一部分延伸在外部。

#### 6. 证明一个新问题 $L$ 是 NP-完全问题的步骤
1. 步骤一：证明该问题本身属于 NP，即 $L \in NP$。
2. 步骤二：找一个**已知**是 NP-完全的问题 $L'$，证明 $L' \le_p L$（即在多项式时间内，将 $L'$ 的实例构建为 $L$ 的实例）。

#### 7. 经典 NPC 问题深度剖析

* **A. 可满足性 (SAT) 问题 —— 第一个 NPC 问题**
  * **描述**：给出一个合取范式（CNF）公式 $F$，问是否存在一组布尔变量的真值指派，使得 $F$ 的结果为真（True）。
  * **CNF 结构**：由变量及它们的非（文字）组成的析取式（“或”关系 $\vee$）通过合取（“与”关系 $\wedge$）连接而成的公式。例如 $F = A_1 \wedge A_2 \wedge \dots \wedge A_k$。
  * **实例对比**：
    * $F_1 = (x_1 \vee x_2) \wedge (\neg x_1 \vee x_2 \vee x_3) \wedge \neg x_2$：令 $(1, 0, 1)$ 可使公式为真，它是**可满足的**。
    * $F_2 = (x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2 \vee x_3) \wedge x_2 \wedge \neg x_3$：不存在任何成真赋值，**不可满足**。
  * **不确定算法**：猜想阶段用 `choice(true, false)` 为各个变量指派真值，验证阶段直接计算 $F$ 的值，总复杂度为 $O(n)$。
  * **Cook 定理**：证明了 SAT 是第一个 NP-完全问题（任何 NP 问题都可以多项式时间归约到 SAT）。以此为根基，SAT 衍生归约出了 3SAT、最大可满足性、恰好覆盖、子集和、0/1背包等，目前 NPC 问题已超 3000 个。

* **B. 恰好覆盖问题**
  * **描述**：给定有穷集 $A = \{a_1, a_2 \dots a_n\}$ 以及 $A$ 的子集的集合 $W = \{S_1, S_2 \dots S_m\}$。寻找一个 $U \subseteq W$，若 $U$ 中的子集彼此**互不相交**且它们的**并集恰好等于 $A$**，则称 $U$ 是 $A$ 的恰好覆盖。
  * **实例**：$A=\{1,2,3,4,5\}$，$W=\{S_1,S_2,S_3,S_4\}$，其中 $S_1=\{1,2\}$, $S_2=\{1,3,4\}$, $S_3=\{2,4\}$, $S_4=\{2,5\}$。由于 $S_2$ 和 $S_4$ 不相交且并集为 $A$，所以 $\{S_2, S_4\}$ 是恰好覆盖。若把 $S_4$ 改为 $\{3,5\}$，则覆盖不存在。该问题已被证是 NPC 的。

* **C. 子集和问题**
  * **描述**：给定正整数集合 $X=\{x_1, x_2 \dots x_n\}$ 及正整数 $N$，问是否存在一个子集 $T \subseteq X$，使得 $T$ 中元素的和恰好等于 $N$。
  * **证明其为 NPC 的思想（恰好覆盖 $\le_p$ 子集和）**：
    * **构造方法**：设恰好覆盖中 $A$ 有 $n$ 个元素，$W$ 有 $m$ 个子集。我们将子集和中的数字 $x_j$ 和 $N$ 统一构造为含有 $n$ 个分段的二进制数，每个分段占用 $k$ 位，其中 $k = \lceil \log_2(m+1) \rceil$。
    * **目标 $N$ 的构造**：使 $N$ 的每一个分段的最右边一位都是 1。
    * **数字 $x_j$ 的构造**：对应集合 $W$ 中的子集 $S_j$。如果元素 $a_i \in S_j$，则 $x_j$ 的第 $i$ 个分段的最右位填 1，否则全填 0。
    * **为什么要 $k$ 位？**：因为在求子集和时，最多会有 $m$ 个数相加。设计 $k = \lceil \log_2(m+1) \rceil$ 位可以彻底**保证各个分段在相加时不会向前进位**，从而污染上一段。
    * **构造举例**：
      原始恰好覆盖实例：$A=\{a_1, a_2, a_3, a_4\}=\{2,3,5,8\}$；$W=\{S_1, S_2, S_3\}$，其中 $S_1=\{a_1, a_2\}$，$S_2=\{a_1, a_3, a_4\}$，$S_3=\{a_2\}$。显而易见 $S_2 \cup S_3$ 是全覆盖。
      转化为子集和：$n=4, m=3 \rightarrow k = 2$。
      目标 $N = 01010101$（4段，每段2位且低位为1）。
      根据元素包含关系转为二进制：
      $x_1 = 01010000$（包含 $a_1, a_2$）
      $x_2 = 01000101$（包含 $a_1, a_3, a_4$）
      $x_3 = 00010000$（包含 $a_2$）
      最终可得：$x_2 + x_3 = N$，完美的完成了多项式时间内的转化。

---

### 四... 9.4 小结

PPT 的最后对全章的核心理论进行了高屋建瓴的总结：

* **P-问题**：所有能在多项式时间内用**确定算法**求解的判定问题集合。
* **NP-问题**：所有能在多项式时间内用**不确定算法**求解（猜想+验证）的判定问题集合。
* **NP-完全问题 (NPC)**：一类极其特殊的 NP 问题。只要能证明 NPC 中的任意一个问题属于 P 问题（即存在多项式确定算法），那么所有 NP 问题就全都是 P 问题（即 $P=NP$）。
* **SAT 问题的历史地位**：它是第一个被发现的 NP-完全问题，后续的所有 NPC 问题都是从它开始不断归约出来的。
* **严格定义**：
  * **NPC 问题 $L$**：必须满足 $L \in NP$，且满足 $\text{SAT} \le_p L$。
  * **NP-难问题 $L$**：只需要满足 $\text{SAT} \le_p L$（不强制要求属于 NP）。
* **归约的终极目的**：通过不断的归约，去寻找那些“复杂度不会降低、但应用范围更广”的通用算法，来代替那些“复杂度低、但应用范围狭窄”的特定问题算法。

---

以上就是这份 PPT 的全部详细内容了。它从最基础的时间复杂度、好算法的定义聊起，通过不确定机模型无缝过渡到 P/NP 体系，最后用严密的二进制分段构造法向你展示了 NPC 问题之间是如何进行多项式时间归约的。希望这份梳理能帮你看清、讲透整章的逻辑脉络！