e2hang/Data-Structure

Fork 0

Files

e2hang 5dd5661e3a New Exam

2026-06-20 19:58:54 +08:00

17 KiB

Raw Permalink Blame History

第九章 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$。

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 保存结果。
代码逻辑：

  // 构造/猜想阶段：复杂度 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)

代码逻辑：

// 不确定阶段：从 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-完全问题的步骤

步骤一：证明该问题本身属于 NP，即 $L \in NP$。
步骤二：找一个已知是 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 问题之间是如何进行多项式时间归约的。希望这份梳理能帮你看清、讲透整章的逻辑脉络！

17 KiB Raw Permalink Blame History Unescape Escape