CS170 · 第 9 讲

NP 完全问题

本章是全书的转折点：在经历了七章高效算法之后，我们直面那些历经数十年仍未找到多项式时间解法的计算问题。我们将建立 NP 完全性理论，揭示这些看似迥异的难解问题本质上是同一问题的不同伪装，并展示如何通过多项式时间归约将它们串联成一个紧密的网络。

学习目标

• 理解搜索问题的形式化定义：实例 I、解 S、多项式时间验证算法 C(I,S)
• 区分 P 类（多项式时间可解）与 NP 类（多项式时间可验证）的计算复杂性差异
• 掌握多项式时间归约 A → B 的结构：实例变换 f 与解回推 h
• 理解 NP 完全问题的定义及其作为“最难搜索问题”的地位
• 能够描述 SAT、3SAT、独立集、顶点覆盖、3D 匹配、ZOE、Rudrata 环、TSP 等经典问题之间的归约链
• 了解归约在证明问题计算困难性中的核心作用，以及不可解问题（停机问题）与 NP 完全问题的本质区别

先修回顾

• 贪心算法与动态规划的基本思想与应用场景
• 图论基本概念：顶点、边、路径、环、连通分量、度
• 线性规划与整数线性规划的基本形式（第 7 章）
• 多项式时间与指数时间复杂度的分析方法
• 归约的基本思想：将一个问题的求解转化为另一个问题的求解（第 7 章）

搜索问题导论：指数爆炸与多项式效率

本章的核心研究对象是搜索问题（search problem）：给定一个实例 I（输入数据），寻找一个满足特定规格的对象 S（解），或报告不存在这样的解。

本书前七章讨论的最短路径、最小生成树、最大流、最大匹配等问题，虽然候选解空间呈指数级增长——\(n\) 个男孩与 \(n\) 个女孩有 \(n!\) 种匹配方式、\(n\) 个顶点的图有 \(n^{n-2}\) 棵生成树——但都找到了巧妙绕过穷举搜索的高效算法。这些算法的运行时间是输入大小的多项式函数（如 \(n\)、\(n^2\)、\(n^3\)）。

然而本章引入的新问题，至今未发现任何显著优于穷举搜索的多项式时间算法。为了理解这种困难性的深远意义，我们先考察指数增长的威力。

指数增长的寓言：根据传说，国际象棋发明者 Sissa 请求国王在棋盘第一格放 1 粒米、第二格 2 粒、第三格 4 粒，依此类推翻倍至第 64 格。总数为

\[2^{64} - 1 = 18\,446\,744\,073\,709\,551\,615\]

足以将印度铺满好几遍。Malthus 由此论证人口的指数增长终将耗尽线性增长的资源；Moore 则观察到芯片晶体管密度每 18 个月翻番，这便是 Moore 定律。

摩尔定律的两面性：表面上看，硬件的指数级进步似乎让指数时间算法变得可接受——只需等待即可。但事实恰恰相反。假设一个 \(O(2^n)\) 的布尔可满足性（SAT）算法运行 1 小时，1975 年可解 25 个变量、1985 年 31 个、1995 年 38 个、如今约 45 个——每增加一个变量需等待约 1.5 年，而应用需求的增速远超于此。相比之下，\(O(n)\) 或 \(O(n\log n)\) 算法每十年可处理的问题规模乘以约 \(100\) 倍；\(O(n^2)\) 算法乘以约 \(10\) 倍；即便是 \(O(n^6)\) 这样不够优雅的多项式算法，每十年也能将可解规模翻倍有余。

这一反转揭示了一个深刻事实：指数算法在摩尔定律下仅能取得多项式级别的进展，而多项式算法则能取得指数级别的进展。要让摩尔定律真正转化为解决问题的能力，我们需要高效的多项式算法。

搜索问题的形式化：

一个搜索问题由以下性质定义：对于实例 I，存在一个验证算法 \(C(I, S)\)，当且仅当 S 是 I 的解时输出 \(\text{true}\)，且 \(C\) 在 \(|I|\) 的多项式时间内运行。此外，解 S 的长度必须是 \(|I|\) 的多项式（以保证可读性）。

以 SAT 为例：\(I\) 是一个合取范式（CNF）布尔公式，\(S\) 是一个真值赋值，验证算法只需检查 \(S\) 是否使每个子句中至少一个文字为 \(\text{true}\)，这显然是多项式时间的。

从 SAT 到 TSP：经典难解问题巡礼

本节系统介绍一系列重要的搜索问题，其中一些问题我们已在前面章节见过高效算法，而另一些则因微小的结构差异变得极其困难。

布尔可满足性 SAT 与 3SAT

SAT 的实例是合取范式（CNF）公式，即若干子句的合取，每个子句是若干文字的析取（文字 = 变量或其否定）。例如：

\[(x \lor y \lor z) \land (x \lor y) \land (\lnot y \lor z) \land (\lnot z \lor x) \land (x \lor y \lor z)\]

SAT 要求找到使每个子句至少有一个文字为真的赋值。对于 \(n\) 个变量，朴素算法需检查 \(2^n\) 种赋值。

SAT 有两个多项式时间可解的特例：Horn SAT（每个子句至多一个正文字，可用贪心算法求解）和 2SAT（每个子句两个文字，可通过强连通分量在线性时间求解）。然而一旦允许子句包含三个文字，得到的 3SAT 问题就再次变得困难。

旅行商问题 TSP

给定 \(n\) 个城市及其两两之间的距离 \(d_{ij}\)，以及预算 \(b\)，寻找一条恰好访问每个城市一次并返回起点的回路（tour），使其总长度 \(\leq b\)。TSP 原本是优化问题（求最短回路），但我们将其改写为搜索问题以便统一框架：优化版本可通过二分搜索调用搜索版本来求解（见习题 8.1）。

TSP 与最小生成树（MST）形成鲜明对比：MST 是多项式时间可解的，而 TSP 可视为 MST 的"困难表亲"——TSP 要求树不能分叉（即为一条路径/环），这一结构限制显著增加了复杂度。

Euler 路径与 Rudrata 环

Euler 路径访问每条边恰好一次，其多项式时间可解性由 Euler 刻划：连通且至多两个顶点度数为奇数。

Rudrata 环（Hamilton 环）访问每个顶点恰好一次，与 TSP 惊人地相似，至今未有多项式时间算法。Euler 问题与 Rudrata 问题的复杂度鸿沟源于"边 vs 顶点"的差异，而非"路径 vs 环"的差异（后者可通过简单归约等价化）。

割与平衡割

最小割（Min-Cut）可通过 \(n-1\) 次最大流计算在多项式时间求解。但平衡割（Balanced Cut）要求将顶点分为两个大小均 \(\geq n/3\) 的集合且割边数 \(\leq b\)，这是一个困难问题，在图像分割等应用中有重要价值。

整数线性规划 ILP 与零一方程 ZOE

ILP 要求整数向量 \(x\) 满足 \(Ax \leq b\)，即使 LP 有多项式时间算法，ILP 仍是困难的。ZOE 是 ILP 的特例：寻找 0-1 向量 \(x\) 使 \(Ax = \mathbf{1}\)（\(A\) 为 0-1 矩阵），其简洁形式在归约理论中极有价值。

3D 匹配

二分匹配（男孩-女孩）可归约为最大流而高效求解。3D 匹配引入第三维度（男孩-女孩-宠物），要求找出 \(n\) 个不相交的三元组覆盖所有成员，这一微小推广使其变为困难问题。

独立集、顶点覆盖、团

独立集（Independent Set）要求 \(g\) 个两两不相邻的顶点；顶点覆盖（Vertex Cover）要求 \(b\) 个覆盖所有边的顶点；团（Clique）要求 \(g\) 个两两相邻的顶点。三者在一般图上均为困难问题，在树上独立集可高效求解。

最长路径与背包问题

最短路径可高效求解，但最长路径（简单路径、总权重 \(\geq g\)）是困难的。背包问题（Knapsack）的 \(O(nW)\) 动态规划在输入规模上是指数级的（因涉及 \(W\) 而非 \(\log W\)）。子集和（Subset Sum）是背包的特例（价值=权重、目标=容量），同样困难。

下表总结了困难问题（NP 完全）与容易问题（在 P 中）的对比：

P 与 NP：多项式时间可解与可验证

为精确讨论计算复杂性，我们引入两个核心复杂性类。

P 类（Polynomial time）

P 是所有可在多项式时间内求解的搜索问题的集合。即存在算法，输入实例 \(I\)，在 \(O(|I|^k)\) 时间内返回一个解 \(S\)（如果存在），或正确报告无解。前一章讨论的最短路径、最小生成树、最大流等问题均属于 P。

NP 类（Nondeterministic Polynomial time）

NP 是所有多项式时间可验证的搜索问题的集合。即存在验证算法 \(C(I, S)\)，当且仅当 \(S\) 是 \(I\) 的解时输出 \(\text{true}\)，且运行时间为 \(|I|\) 的多项式。

NP 名称源于"非确定性多项式时间"：想象一种能在每一步正确猜测的非确定性算法，它能在多项式时间内找到一个解并验证。这等价于"多项式时间可验证"的搜索问题定义。

历史注记：NP 最初定义为判定问题（是/否问题）的类，源于形式语言理论的研究传统。搜索问题版本与其本质相通。

P 与 NP 的关系

显然 \(\text{P} \subseteq \text{NP}\)：若一个问题可在多项式时间求解，则给出解后自然可在多项式时间验证（只需求解并比较）。核心问题是反向包含是否成立：\(\text{P} \stackrel{?}{=} \text{NP}\)。

绝大多数研究者相信 \(\text{P} \neq \text{NP}\)。理由包括：数十年来无数聪明头脑未能找到这些困难问题的多项式算法；数学定理的"寻找证明"是一个搜索问题且属于 NP——若 \(\text{P} = \text{NP}\)，则将存在高效方法证明任何定理，数学家就不再被需要了。

然而证明 \(\text{P} \neq \text{NP}\) 本身极其困难，是数学和计算机科学中最重要的未解难题之一。

搜索问题的空间结构

假设 \(\text{P} \neq \text{NP}\)，搜索问题的空间可想象为一个从易到难的谱系：底部是 P（多项式时间可解），顶部是 NP 完全（NP 中最难的问题），中间可能存在既非 P 也非 NP 完全的问题（如因数分解）。

function VerifySAT(I, S):
    // I = CNF 公式, S = 真值赋值
    for each clause C in I:
        clause_satisfied = false
        for each literal l in C:
            if l is variable x and S[x] == true:
                clause_satisfied = true
            if l is negated variable not-x and S[x] == false:
                clause_satisfied = true
        if clause_satisfied == false:
            return false
    return true

归约与 NP 完全性

要证明某个问题没有高效算法，我们需要比"尚未发现算法"更强有力的证据。归约（reduction） 提供了这种证据。

搜索问题的归约

从搜索问题 A 到搜索问题 B 的归约由两个多项式时间算法组成：

• \(f\)：将 A 的任意实例 \(I\) 变换为 B 的实例 \(f(I)\)；

• \(h\)：将 B 的任意解 \(S\)（针对 \(f(I)\)）回推为 A 的解 \(h(S)\)（针对 \(I\)）。

必须满足：\(f(I)\) 有解当且仅当 \(I\) 有解；若 \(f(I)\) 无解，则 \(I\) 也无解。

归约的图示：

I ──f──> f(I)
│          │
│ h        │ 算法 for B
│          │
h(S) <── S ──

这意味着：任何求解 B 的算法都可被"夹在" \(f\) 和 \(h\) 之间，转化为求解 A 的算法。

归约的方向

若记归约为 \(A \to B\)，则：

• 困难性沿箭头方向传播：若 A 困难且 \(A \to B\)，则 B 也困难。

• 高效算法逆箭头方向传播：若 B 有多项式算法且 \(A \to B\)，则 A 也有多项式算法。

在本章中，我们使用归约的"反常"目的：已知 A 困难，通过 \(A \to B\) 证明 B 也困难。

归约的复合

归约具有传递性：若 \(A \to B\) 且 \(B \to C\)，则 \(A \to C\)。复合归约的前处理为 \(f_{BC} \circ f_{AB}\)，后处理为 \(h_{AB} \circ h_{BC}\)。这使得归约链可以高效地扩展 NP 完全性的证明范围。

NP 完全的定义

一个搜索问题是 NP 完全的（NP-complete），当且仅当所有其他搜索问题都可归约到它。这是一个极强的要求：NP 完全问题必须能用来解决世界上任何搜索问题！

NP 完全问题的存在令人惊讶，但确实存在。一旦我们证明某个问题是 NP 完全的，就可用它证明新的 NP 完全问题：只需将已知的 NP 完全问题归约到新问题即可。

归约证明困难性的逻辑

所有 NP 问题都归约到 NP 完全问题，因此每个 NP 完全问题都包含了所有搜索问题的复杂性。若任何一个 NP 完全问题属于 P，则 \(\text{P} = \text{NP}\)。既然我们相信 \(\text{P} \neq \text{NP}\)，这些搜索问题就都是困难的。

因数分解的不同

因数分解（FACTORING）也是著名的困难问题，但其困难性质与 NP 完全问题不同。因数分解总是有解（任何整数都可分解为素数乘积），且未被相信是 NP 完全的。第 10 章将展示因数分解可被量子计算机高效求解，而 SAT、TSP 等 NP 完全问题似乎不能。

核心归约链（上）：布尔逻辑与图论之间的桥梁

本节展示两个关键归约：3SAT 到独立集、SAT 到 3SAT，以及独立集与顶点覆盖、团之间的简单归约。

3SAT \(\to\) INDEPENDENT SET

这是连接布尔逻辑与图论的关键归约。给定 3SAT 实例 \(I\)，构造独立集实例 \((G, g)\)：

1. 对每个子句（如 \((x \lor y \lor z)\)），在 \(G\) 中创建一个三角形，顶点标号为 \(x, y, z\)（两文字子句创建一条边）。
2. 对任意两个代表相反文字（\(x\) 与 \(\lnot x\)）的顶点，添加一条边。
3. 设目标 \(g\) = 子句数量。

为什么这样构造？

• 三角形的最大独立集大小为 1，因此独立集从每个子句至多选一个文字。

• \(g\) 等于子句数，迫使独立集恰好从每个子句选一个文字。

• 相反文字之间的边防止矛盾赋值（不能同时选 \(x\) 和 \(\lnot x\)）。

解的回推：若独立集 \(S\) 有 \(g\) 个顶点，则对每个变量 \(x\)：若 \(S\) 含标号 \(x\) 的顶点，令 \(x = \text{true}\)；若含 \(\lnot x\)，令 \(x = \text{false}\)；否则任意赋值。此赋值满足所有子句。

反之，若有满足赋值，从每个子句选一个为真的文字加入 \(S\)，则 \(S\) 是大小为 \(g\) 的独立集。

SAT \(\to\) 3SAT

这是"问题归约为自身特例"的典范。要将 SAT 归约为 3SAT，只需消除长文字子句。对子句 \((a_1 \lor a_2 \lor \ldots \lor a_k)\)（\(k > 3\)），引入新变量 \(y_1, y_2, \ldots, y_{k-3}\)，替换为：

\[(a_1 \lor a_2 \lor y_1) \land (\lnot y_1 \lor a_3 \lor y_2) \land \cdots \land (\lnot y_{k-3} \lor a_{k-1} \lor a_k)\]

等价性证明：

• 若新子句全满足，则某个 \(a_i\) 必为真（否则 \(y_1\) 真 \(\Rightarrow\) \(y_2\) 真 \(\Rightarrow\) ... \(\Rightarrow\) 最后一子句假）。

• 若原子句满足（某 \(a_i\) 真），令 \(y_1, \ldots, y_{i-2}\) 为真，其余为假，即可满足所有新子句。

进一步可限制每个文字至多出现两次：将变量 \(x\) 的 \(k\) 次出现替换为 \(x_1, \ldots, x_k\)，并添加等价链 \((x_1 \lor x_2) \land (x_2 \lor x_3) \land \cdots \land (x_k \lor x_1)\)。

INDEPENDENT SET \(\to\) VERTEX COVER

基于补集关系：\(S\) 是顶点覆盖 \(\iff\) \(V \setminus S\) 是独立集。

因此，要判断图 \(G\) 是否有大小为 \(g\) 的独立集，只需检查是否存在大小为 \(|V| - g\) 的顶点覆盖。

INDEPENDENT SET \(\to\) CLIQUE

基于补图关系：\(S\) 是 \(G\) 的独立集 \(\iff\) \(S\) 是补图 \(\overline{G}\) 的团。

因此将实例 \((G, g)\) 映射为 \((\overline{G}, g)\)，解完全相同。

核心归约链（下）：从匹配、方程到环与旅行商

本节继续沿归约链深入：3SAT 到 3D 匹配、3D 匹配到 ZOE、ZOE 到子集和、ZOE 到 ILP，以及 ZOE 到 Rudrata 环再到 TSP。

3SAT \(\to\) 3D MATCHING

这是归约理论中最精巧的构造之一，需要用三元组模拟布尔变量和逻辑门。

变量 gadget：对每个变量 \(x\)，创建两个男孩 \(b_0, b_1\)、两个女孩 \(g_0, g_1\) 和四个宠物 \(p_0, p_1, p_2, p_3\)，组成四个三元组构成的"菱形"结构。任何匹配必须选择其中两组：\((b_0, g_1, p_0), (b_1, g_0, p_2)\)（表示 \(x=\text{true}\)）或 \((b_0, g_0, p_1), (b_1, g_1, p_3)\)（表示 \(x=\text{false}\)）。

子句 gadget：对子句 \(c = (x \lor y \lor z)\)，创建新男孩 \(b_c\) 和新女孩 \(g_c\)，添加三个三元组对应三种满足方式（\(x=\text{true}\)、\(y=\text{false}\)、\(z=\text{true}\)），每个三元组使用变量 gadget 中特定的宠物。若文字为真，对应宠物空闲可用；若为假，宠物已被占用，无法匹配。

收尾：未匹配的宠物通过"通用动物爱好者"夫妇来匹配。

3D MATCHING \(\to\) ZOE

ZOE 的 0-1 变量天然描述组合选择：对每个三元组 \(i\)，设 \(x_i \in \{0,1\}\)（选中为 1）。对每个男孩/女孩/宠物，写方程 \(\sum_{j \in T} x_j = 1\)（\(T\) 是该实体出现的三元组集合），要求恰好一个三元组被选中。这直接得到 \(Ax = \mathbf{1}\) 形式。

ZOE \(\to\) SUBSET SUM

关键观察：0-1 向量可编码为整数。将 \(A\) 的每列视为二进制整数，寻找列的子集使其和为 \(\mathbf{1}\)（全 1 向量）对应子集和问题。

但二进制加法有进位问题！解决方案：将列视为 base \((n+1)\) 整数（\(n\) 为列数）。由于至多 \(n\) 个数相加且每位数字为 0 或 1，base \((n+1)\) 下不会产生进位，向量加法与整数加法等价。

ZOE \(\to\) ILP

ILP 要求整数向量 \(x\) 满足 \(Ax \leq b\)。将 ZOE 的每个方程 \(x_{j_1} + \cdots + x_{j_k} = 1\) 拆为两个不等式 \(\leq 1\) 和 \(\geq 1\)，并添加 \(0 \leq x_i \leq 1\)，即得 ILP 形式。

ZOE \(\to\) RUDRATA CYCLE

分两步：先归约为带边对 Rudrata 环（Rudrata Cycle with Paired Edges），再消除边对。

ZOE 到带边对 Rudrata 环：构造一个包含 \(m+n\) 组平行边的简单环结构（\(m\) 个方程、\(n\) 个变量）。每组平行边选择一个，对应变量赋值或方程中选择哪个变量。边对约束 \(C\) 确保：若变量 \(x_i=1\)（选择 \(x_i=1\) 边），则方程侧不能选 \(x_i\) 相关边（因与 \(x_i=0\) 边配对），从而保证每个方程恰好一个变量为 1。

消除边对：设计一个 12 顶点 gadget（图 8.12），在 Rudrata 环中只能以两种方式遍历，模拟一对边中恰好选一条的约束。替换所有边对后得到纯 Rudrata 环。

RUDRATA CYCLE \(\to\) TSP

给定图 \(G=(V,E)\)，构造 TSP：城市 = \(V\)，距离 \(d_{uv} = 1\) 若 \(\{u,v\} \in E\)，否则 \(d_{uv} = 1+\epsilon\)（\(\epsilon > 1\)），预算 \(b = |V|\)。

• 若 \(G\) 有 Rudrata 环，则同一回路是 TSP 中长度 \(= |V| \leq b\) 的 tour。

• 若 \(G\) 无 Rudrata 环，则任何 TSP tour 至少用一条非边（长度 \(1+\epsilon\)），总长度 \(\geq |V| + \epsilon > b\)。

取 \(\epsilon = 1\) 得满足三角不等式的 TSP（第 9 章可近似）；取 \(\epsilon\) 大则产生"间隙"性质：要么有长度 \(\leq n\) 的解，要么所有解长度 \(\geq n + \epsilon\)（间隙），这蕴含不可近似性（除非 \(\text{P} = \text{NP}\)）。

所有 NP 问题皆可归约为 SAT 与不可解问题

本节完成归约链的闭环：证明所有 NP 问题都可归约到 SAT，从而确立 SAT 的 NP 完全性，并简要讨论超越 NP 的不可解问题。

CIRCUIT SAT：SAT 的推广

CIRCUIT SAT 的实例是一个布尔电路（有向无环图），包含五种门：AND（入度 2）、OR（入度 2）、NOT（入度 1）、已知输入（标号 \(\text{true}\)/\(\text{false}\)）、未知输入（标号 \(?\)）。一个汇点被指定为输出门。

CIRCUIT SAT 要求找到未知输入的赋值使输出门为 \(\text{true}\)。

CIRCUIT SAT 归约为 SAT

对每个门 \(g\) 引入变量，用子句模拟门的行为：

• NOT 门 \(g = \lnot h\)：子句 \((g \lor h) \land (\lnot g \lor \lnot h)\)（\(g \iff \lnot h\)）。

• AND 门 \(g = h_1 \land h_2\)：子句 \((\lnot g \lor h_1) \land (\lnot g \lor h_2) \land (g \lor \lnot h_1 \lor \lnot h_2)\)。

• OR 门类似。

• 输出门 \(g\)：添加子句 \((g)\) 强制其为真。

所得 CNF 公式的满足赋值与电路满足赋值一一对应。

任意 NP 问题归约为 CIRCUIT SAT

这是通用归约：设 \(A\) 是任意 NP 问题，\(C(I, S)\) 是其多项式时间验证算法。

关键论证（第 7.7 节）：任何多项式时间算法都可表示为电路——输入门编码输入比特，门的数量是输入规模的多项式。

因此，对 \(A\) 的实例 \(I\)，可在多项式时间构造电路：已知输入 = \(I\) 的比特，未知输入 = \(S\) 的比特，输出 = \(\text{true} \iff S\) 是 \(I\) 的解。此电路的满足赋值与 \(I\) 的解一一对应。

归约链闭环：

\[\forall A \in \text{NP}: A \to \text{CIRCUIT SAT} \to \text{SAT} \to \text{3SAT} \to \cdots\]

这证明了 CIRCUIT SAT 和 SAT 是 NP 完全的：所有 NP 问题都可归约到它们。

不可解问题

NP 完全问题至少还有指数时间算法。但存在完全没有算法的合理计算问题！

停机问题（Halting Problem）：给定程序 \(p\) 和输入 \(x\)，判断 \(p(x)\) 是否停机。

Turing 1936 年的证明：假设存在程序 \(\text{terminates}(p, x)\)，构造

function paradox(z):
    if terminates(z, z) goto loop  // 若 z(z) 停机则循环
    otherwise halt                  // 否则停机

执行 \(\text{paradox}(\text{paradox})\)：若它停机 \(\Rightarrow\) \(\text{terminates}(\text{paradox}, \text{paradox}) = \text{true}\) \(\Rightarrow\) 它循环，矛盾；若它循环 \(\Rightarrow\) \(\text{terminates} = \text{false}\) \(\Rightarrow\) 它停机，矛盾。故 \(\text{terminates}\) 不存在。

这展示了计算的极限：有些问题无论多少时间都无法通过算法解决。编程永远需要纪律、创造力和技巧——你无法自动检测程序是否有无限循环。

交互推演

以 3SAT 到 CLIQUE 为例逐项审查归约方向、构造、双向等价与 NP 成员性。

依据本地课程资料 lectures/chap8.pdf、dis10.pdf、dis11.pdf、dis12.pdf 重绘；交互用于解释算法状态与证明不变量，不替代正文中的完整论证。

常见误区

知识检查

本讲要点

• 搜索问题由多项式时间验证算法 C(I,S) 定义：给定实例 I 和候选解 S，可在多项式时间判断 S 是否为有效解
• P 类 = 多项式时间可解的搜索问题；NP 类 = 多项式时间可验证的搜索问题；P ⊆ NP，但是否相等是核心开放问题
• 归约 A → B 由实例变换 f 和解回推 h 组成，两者均为多项式时间；困难性沿箭头方向传播，算法效率逆箭头方向传播
• NP 完全问题 = 所有 NP 问题都可归约到它的问题；若任一 NP 完全问题 ∈ P，则 P = NP
• 归约链：3SAT → 独立集 → 顶点覆盖/团；3SAT → 3D 匹配 → ZOE → 子集和/ILP → Rudrata 环 → TSP
• 所有 NP 问题可归约到 CIRCUIT SAT，再归约到 SAT，完成 NP 完全性的闭环证明
• 不可解问题（停机问题）超越了 NP：无论多少时间都无法通过算法解决，这是计算的固有极限

一手资料

• lectures/chap8.pdf · 247-249 · confidence: high · 定义搜索问题由多项式时间算法 C 指定：C(I,S)=true ⟹ S 是 I 的解；摩尔定律下指数算法仅多项式进展而多项式算法指数进展
• lectures/chap8.pdf · 258-260 · confidence: high · P 是所有多项式时间可解的搜索问题；NP 由验证算法定义；归约图示含 f 和 h 两个多项式时间函数；NP 完全定义：所有其他搜索问题归约到它
• lectures/chap8.pdf · 263-267 · confidence: high · 3SAT 到独立集：每个子句创建三角形，相反文字连边，目标 g=子句数；SAT 到 3SAT：长子句 (a1∨...∨ak) 用新变量 y1...yk-3 拆分为多个三文字子句
• lectures/chap8.pdf · 267-274 · confidence: high · 3D 匹配 ZOE 形式化：变量 xi∈{0,1} 表示第 i 个三元组是否选中，每行方程保证每个男孩/女孩/宠物恰好出现一次；ZOE 到子集和用 base n+1 避免进位
• lectures/chap8.pdf · 274-276 · confidence: high · 通用归约：对 NP 问题 A 的实例 I，构造电路使已知输入编码 I、未知输入编码 S，输出 true ⟺ S 是 I 的解；CIRCUIT SAT 到 SAT 通过门级 CNF 编码实现