cover.png#NP 完全性与归约

前面的大多数算法问题都可以在多项式时间内求解，例如：

• 排序：\(O(n\log n)\)
• 最短路：\(O(E\log V)\) 或 \(O(VE)\)
• 最大流：\(O(VE^2)\)、\(O(V^2E)\) 等
• 动态规划中的很多问题：\(O(n^2)\)、\(O(nW)\) 等

但并不是所有自然问题都有已知的多项式时间算法。例如：

• TSP：访问每个点恰好一次的最短回路，典型 DP 算法为 \(O(n^2 2^n)\)
• Clique：寻找最大团，朴素搜索级别约为 \(O(n2^n)\)

几十年来没有人找到这些问题的多项式时间算法，也没有人证明它们一定不存在。NP 完全性理论的作用是说明：大量看似不同的困难问题，本质上是等价的。

---

判定问题

复杂性理论中通常研究判定问题，即答案只有 YES 或 NO 的问题。

优化问题可以转化为判定版本：

优化问题	判定版本
TSP 最短回路长度是多少	是否存在长度 \(\leq K\) 的 TSP 回路
最大团大小是多少	是否存在大小 \(\geq K\) 的团
最小顶点覆盖大小是多少	是否存在大小 \(\leq K\) 的顶点覆盖

如果一个优化问题能在多项式时间内求最优值，那么它的判定版本也能在多项式时间内求解。很多时候，判定版本的困难性已经足够说明原优化问题困难。

---

P 与 NP

P

一个判定问题 \(\Pi\) 属于 \(\text{P}\)，如果存在多项式时间算法 \(A\)，使得对任意输入 \(x\)：

\[ \Pi(x)=\text{YES}\iff A(x)=\text{YES} \]

也就是说，\(\text{P}\) 是可以在多项式时间内直接求解的问题类。

NP

一个判定问题 \(\Pi\) 属于 \(\text{NP}\)，如果存在多项式时间验证算法 \(V(\cdot,\cdot)\)，使得对任意输入 \(x\)：

\[ \Pi(x)=\text{YES} \iff \exists y,\ |y|\leq \text{poly}(|x|),\ V(x,y)=\text{YES} \]

这里 \(y\) 称为证书 (certificate) 或 witness。

直观理解：

• \(\text{P}\)：能在多项式时间内自己找到答案
• \(\text{NP}\)：如果有人给出一个候选答案，能在多项式时间内验证它是否正确

显然：

\[ \text{P}\subseteq \text{NP} \]

因为能求解的问题一定能验证：直接忽略证书，运行原算法即可。

例子

Clique 判定问题：

输入图 \(G=(V,E)\) 和整数 \(K\)，问是否存在 \(C\subseteq V\)，满足 \(|C|\geq K\)，且 \(C\) 中任意两点之间都有边。

它属于 NP。证书就是点集 \(C\)，验证时检查：

1. \(|C|\geq K\)
2. 对所有 \(u,v\in C\)，有 \((u,v)\in E\)

验证时间至多 \(O(|C|^2)\)。

排序本身不是判定问题，所以不能直接说排序属于 NP。但“输入序列是否已经有序”是判定问题，并且属于 P，也属于 NP。

---

co-NP 与证书的不对称性

NP 只要求 YES 实例有短证书，并不要求 NO 实例也有短证书。

定义 \(\text{co-NP}\)：

一个判定问题 \(\Pi\) 属于 \(\text{co-NP}\)，如果它的补问题 \(\overline{\Pi}\) 属于 NP。

也就是说，\(\Pi\) 的 NO 实例有多项式大小证书，并且可以多项式时间验证。

例子

SAT 属于 NP：

• YES 证书：一个满足赋值
• 验证：代入公式检查是否为真

UNSAT 属于 co-NP：

• 问题：公式是否不可满足
• 若答案为 NO，即公式可满足，则一个满足赋值可以作为证书

但对 UNSAT 的 YES 实例，也就是“公式确实不可满足”，目前不知道是否总有简单的多项式大小证书可以高效验证。

P、NP、co-NP 的关系

显然：

\[ \text{P}\subseteq \text{NP} \]

且：

\[ \text{P}\subseteq \text{co-NP} \]

因为多项式时间可解的问题，YES 和 NO 都可以直接运行算法验证。

但下面两个问题都仍然开放：

\[ \text{P}\stackrel{?}{=}\text{NP} \]

\[ \text{NP}\stackrel{?}{=}\text{co-NP} \]

一般认为：

\[ \text{P}\neq\text{NP} \]

且

\[ \text{NP}\neq\text{co-NP} \]

与 NP-complete 的关系

如果某个 NP-complete 问题同时也在 co-NP 中，那么：

\[ \text{NP}=\text{co-NP} \]

因为所有 NP 问题都能归约到这个问题，而这个问题的补方向也有短证书。

所以在没有证明 \(\text{NP}=\text{co-NP}\) 之前，我们通常不期待 SAT、Clique、Vertex Cover 这些 NP-complete 问题的 NO 实例有简单证书。

这个视角能解释为什么“找一个满足赋值”容易验证，而“证明不存在任何满足赋值”看起来困难得多。

---

多项式时间归约

给定两个判定问题 \(\Pi'\) 和 \(\Pi\)。如果存在一个多项式时间可计算函数 \(f\)，使得对任意输入 \(x'\)：

\[ \Pi'(x')=\Pi(f(x')) \]

则称 \(\Pi'\) 可以多项式时间归约到 \(\Pi\)，记作：

\[ \Pi'\leq_p \Pi \]

意思是：如果会解 \(\Pi\)，就会解 \(\Pi'\)。

算法流程为：

1. 把 \(\Pi'\) 的输入 \(x'\) 用 \(f\) 转换成 \(\Pi\) 的输入 \(x=f(x')\)
2. 调用 \(\Pi\) 的算法求解 \(x\)
3. 返回同样的 YES 或 NO

归约的基本性质

若 \(\Pi'\leq_p \Pi\)，则：

1. 如果 \(\Pi\in\text{P}\)，那么 \(\Pi'\in\text{P}\)
2. 如果 \(\Pi'\notin\text{P}\)，那么 \(\Pi\notin\text{P}\)
3. 归约具有传递性：如果 \(\Pi''\leq_p \Pi'\) 且 \(\Pi'\leq_p \Pi\)，则 \(\Pi''\leq_p \Pi\)

注意证明困难性时的方向：

要证明问题 \(B\) 困难，应该从已知困难问题 \(A\) 出发，证明

\[ A\leq_p B \]

因为这说明如果 \(B\) 容易，那么 \(A\) 也容易。

---

NP-hard 与 NP-complete

一个问题 \(\Pi\) 是 NP-hard，如果对任意 \(\Pi'\in\text{NP}\)，都有：

\[ \Pi'\leq_p \Pi \]

也就是说，\(\Pi\) 至少和 NP 中所有问题一样难。

一个问题 \(\Pi\) 是 NP-complete，如果：

1. \(\Pi\in\text{NP}\)
2. \(\Pi\) 是 NP-hard

所以 NP-complete 问题是 NP 中最难的一批问题。

如果任意一个 NP-complete 问题存在多项式时间算法，那么：

\[ \text{P}=\text{NP} \]

反过来，如果能证明任意一个 NP-complete 问题不在 P 中，那么：

\[ \text{P}\neq\text{NP} \]

目前这仍是开放问题。

证明 NP-complete 的模板

要证明问题 \(B\) 是 NP-complete：

1. 证明 \(B\in\text{NP}\)
2. 选一个已知 NP-complete 问题 \(A\)
3. 构造多项式时间归约 \(A\leq_p B\)
4. 证明归约保持 YES/NO，即 \(x\in A\iff f(x)\in B\)

---

SAT 与 Cook 定理

SAT

SAT (Satisfiability) 问题：

输入一个布尔公式 \(\varphi\)，问是否存在变量的 TRUE/FALSE 赋值，使得 \(\varphi\) 为真。

例如：

\[ (x_1\vee \neg x_2\vee x_5)\wedge (x_3\vee \neg x_5) \]

若存在赋值让每个子句都为真，则公式可满足。

Cook-Levin 定理

Cook 定理说明：

\[ \forall \Pi\in\text{NP},\quad \Pi\leq_p \text{SAT} \]

也就是说，SAT 是 NP-hard 的。

同时 SAT 属于 NP：证书是变量赋值，验证时只需把赋值代入公式并检查是否为真。

因此：

\[ \text{SAT 是 NP-complete} \]

Cook 定理是 NP 完全性理论的起点。之后证明其他问题 NP-complete 时，就不需要从所有 NP 问题出发，只需要从 SAT 或其他已知 NP-complete 问题归约即可。

---

Cook-Levin 定理证明轮廓

把“多项式时间验证过程”编码成一个布尔公式。

证明一般分两步：

1. 证明 Circuit-SAT 是 NP-complete
2. 把 Circuit-SAT 归约到 SAT 或 3SAT

Circuit-SAT

Circuit-SAT 问题：

输入一个由 AND、OR、NOT 门组成的布尔电路，问是否存在输入赋值，使得输出门为 TRUE。

Circuit-SAT 属于 NP：证书是输入赋值，验证时按拓扑序计算每个门的值即可。

任意 NP 问题归约到 Circuit-SAT

设 \(\Pi\in\text{NP}\)，则存在多项式时间验证器 \(V(x,y)\)。

对固定输入 \(x\)，验证器 \(V\) 的运行时间是多项式 \(p(|x|)\)。可以把 \(V\) 的每一步计算展开为一个电路：

• 输入线表示证书 \(y\) 的比特
• 固定常量线表示原输入 \(x\)
• 电路模拟验证器的每一步状态转移
• 输出门表示 \(V(x,y)\) 是否接受

因为 \(V\) 只运行多项式步，所以构造出的电路大小也是多项式。

于是：

\[ x\in \Pi \iff \exists y,\ V(x,y)=1 \iff \text{对应电路可满足} \]

这就得到：

\[ \Pi\leq_p \text{Circuit-SAT} \]

所以 Circuit-SAT 是 NP-hard。

Circuit-SAT 到 SAT

给电路中每条导线或每个门输出引入一个布尔变量。然后用局部约束描述每个门的语义。

例如，若 \(z=x\wedge y\)，可以写成 CNF：

\[ (\neg z\vee x)\wedge(\neg z\vee y)\wedge(z\vee\neg x\vee\neg y) \]

若 \(z=x\vee y\)，可以写成：

\[ (z\vee\neg x)\wedge(z\vee\neg y)\wedge(\neg z\vee x\vee y) \]

若 \(z=\neg x\)，可以写成：

\[ (z\vee x)\wedge(\neg z\vee\neg x) \]

最后再加入输出门变量为 TRUE 的约束。

这样构造的公式大小与电路大小成线性关系，并且公式可满足当且仅当原电路可满足。

因此：

\[ \text{Circuit-SAT}\leq_p \text{SAT} \]

结合前一步，就得到 SAT 的 NP-hard 性。

证明思想

Cook-Levin 定理的关键不是某个具体问题的技巧构造，而是一个通用编码原则：

多项式时间计算可以被多项式大小的布尔公式或布尔电路描述。

这也是为什么 SAT 成为第一个 NP-complete 问题。

---

SAT 归约到 Clique

Clique 问题

输入无向图 \(G=(V,E)\) 和整数 \(K\)，问是否存在点集 \(C\subseteq V\)，满足：

\[ |C|\geq K \]

且对任意不同的 \(u,v\in C\)：

\[ (u,v)\in E \]

这样的点集 \(C\) 称为一个团 (clique)。

构造

给定 SAT 公式：

\[ \varphi=C_1\wedge C_2\wedge\cdots\wedge C_m \]

其中每个 \(C_i\) 是一个子句。

构造图 \(G\)：

1. 对公式中每个文字出现建立一个顶点。文字可以是 \(x_i\) 或 \(\neg x_i\)
2. 两个顶点之间连边，当且仅当：
   • 它们来自不同子句
   • 它们不是互相矛盾的文字，即不是 \(x_i\) 与 \(\neg x_i\)
3. 令 \(K=m\)

这里“文字出现”很重要：同一个文字如果出现在多个子句中，会对应多个顶点。

正确性证明

若 \(\varphi\) 可满足，则 \(G\) 有大小为 \(m\) 的 clique。

取一个使 \(\varphi\) 为真的赋值。因为每个子句都为真，所以每个子句中至少有一个文字为真。从每个子句中选一个为真的文字对应的顶点。

选出的顶点共有 \(m\) 个，并且：

• 任意两个顶点来自不同子句
• 两个为真的文字不可能互相矛盾

所以它们两两相连，构成大小为 \(m\) 的 clique。

若 \(G\) 有大小为 \(m\) 的 clique，则 \(\varphi\) 可满足。

因为同一子句内的顶点之间不连边，所以大小为 \(m\) 的 clique 必须从每个子句中恰好选一个顶点。

又因为互相矛盾的文字之间不连边，所以这些被选中的文字彼此一致，不会同时要求 \(x_i=\text{TRUE}\) 和 \(x_i=\text{FALSE}\)。

于是可以给这些文字赋真值，并任意补全其他变量。每个子句都有一个被选中的真文字，所以 \(\varphi\) 可满足。

结论

归约显然可以在多项式时间内完成，因此：

\[ \text{SAT}\leq_p \text{Clique} \]

因为 SAT 是 NP-complete，Clique 又属于 NP，所以：

\[ \text{Clique 是 NP-complete} \]

---

Clique、Independent Set 与 Vertex Cover

Independent Set

Independent Set (IS) 问题：

输入无向图 \(G=(V,E)\) 和整数 \(K\)，问是否存在 \(S\subseteq V\)，满足：

\[ |S|\geq K \]

且 \(S\) 中任意两点之间都没有边。

这样的点集称为独立集。

Clique 归约到 IS

给定 Clique 输入 \((G,K)\)，构造：

\[ G'=\overline{G},\quad K'=K \]

其中 \(\overline{G}\) 是 \(G\) 的补图。

则：

\[ C \text{ 是 } G \text{ 中大小为 } K \text{ 的 clique} \iff C \text{ 是 } \overline{G} \text{ 中大小为 } K \text{ 的 independent set} \]

因此：

\[ \text{Clique}\leq_p \text{IS} \]

IS 属于 NP，所以 IS 是 NP-complete。

Vertex Cover

Vertex Cover (VC) 问题：

输入无向图 \(G=(V,E)\) 和整数 \(K\)，问是否存在 \(C\subseteq V\)，满足：

\[ |C|\leq K \]

且每条边至少有一个端点在 \(C\) 中。

这样的点集称为顶点覆盖。

IS 归约到 VC

给定 IS 输入 \((G,K)\)，构造：

\[ G'=G,\quad K'=|V|-K \]

核心事实：

\[ S \text{ 是 independent set} \iff V\setminus S \text{ 是 vertex cover} \]

证明：

• 若 \(S\) 是独立集，则没有边的两个端点都在 \(S\) 中，所以每条边至少有一个端点在 \(V\setminus S\) 中
• 若 \(V\setminus S\) 是顶点覆盖，则不存在一条边的两个端点都落在 \(S\) 中，所以 \(S\) 是独立集

因此：

\[ \text{IS}\leq_p \text{VC} \]

VC 属于 NP，所以 VC 是 NP-complete。

归约链

目前已经得到：

\[ \text{SAT}\leq_p \text{Clique}\leq_p \text{IS}\leq_p \text{VC} \]

并且这些问题都属于 NP，所以它们都是 NP-complete。

---

3SAT 归约到 Independent Set

Kleinberg-Tardos、Princeton 算法课等资料常用另一个很经典的归约：

\[ \text{3SAT}\leq_p \text{Independent Set} \]

这个归约和 SAT 到 Clique 的构造很像，只是把“选互不冲突的文字”写成独立集。

构造

给定 3CNF 公式：

\[ \varphi=C_1\wedge C_2\wedge\cdots\wedge C_m \]

每个子句有 3 个文字。

构造图 \(G\)：

1. 对每个子句 \(C_i\) 的 3 个文字建立 3 个顶点
2. 同一个子句内部的 3 个顶点两两相连，形成一个三角形
3. 若两个顶点对应互相矛盾的文字 \(x\) 和 \(\neg x\)，则在它们之间连边
4. 令 \(K=m\)

正确性

若公式可满足，则图中有大小为 \(m\) 的独立集。

从每个子句中选一个为真的文字。因为每个子句内部只能选一个点，而不同子句中被选的真文字不会互相矛盾，所以这些点之间没有边，构成大小为 \(m\) 的独立集。

若图中有大小为 \(m\) 的独立集，则公式可满足。

由于每个子句内部是三角形，独立集最多从每个子句选一个点。大小为 \(m\) 说明它恰好从每个子句选了一个点。

又因为矛盾文字之间有边，独立集中不会同时包含 \(x\) 和 \(\neg x\)。因此可以给选中的文字赋 TRUE，并任意补全其他变量，使每个子句至少有一个真文字。

所以：

\[ \text{3SAT}\leq_p \text{Independent Set} \]

再结合 Independent Set 与 Vertex Cover 的互补关系，可以得到 Vertex Cover 的 NP-complete 性。

---

Exact-3SAT

Exact-3SAT 问题：

输入一个 CNF 公式，其中每个子句恰好有 3 个文字，问公式是否可满足。

例如：

\[ (x_1\vee x_2\vee x_3) \wedge (\neg x_1\vee \neg x_2\vee x_3) \]

SAT 归约到 Exact-3SAT

对 SAT 公式中的每个子句分别处理。

长度为 1 的子句

对子句 \((x)\)，引入新变量 \(y_1,y_2\)，替换为：

\[ (x\vee y_1\vee y_2) \wedge (x\vee y_1\vee \neg y_2) \wedge (x\vee \neg y_1\vee y_2) \wedge (x\vee \neg y_1\vee \neg y_2) \]

这四个子句同时可满足，当且仅当 \(x\) 为真。

长度为 2 的子句

对子句 \((x_1\vee x_2)\)，引入新变量 \(y\)，替换为：

\[ (x_1\vee x_2\vee y) \wedge (x_1\vee x_2\vee \neg y) \]

这要求 \(x_1\vee x_2\) 为真。

长度为 \(k\geq 4\) 的子句

对子句：

\[ (x_1\vee x_2\vee\cdots\vee x_k) \]

引入新变量 \(y_1,\ldots,y_{k-3}\)，替换为：

\[ (x_1\vee x_2\vee y_1) \]

\[ \wedge(\neg y_1\vee x_3\vee y_2) \]

\[ \wedge(\neg y_2\vee x_4\vee y_3) \]

\[ \wedge\cdots \]

\[ \wedge(\neg y_{k-3}\vee x_{k-1}\vee x_k) \]

直观上，\(y_i\) 把“前面还没有出现真文字”的信息传递到后面的子句。新公式可满足当且仅当原长子句可满足。

这个转换只引入线性数量的新变量和新子句，所以是多项式时间归约：

\[ \text{SAT}\leq_p \text{Exact-3SAT} \]

因此 Exact-3SAT 是 NP-complete。

---

图着色

k-Colorability

给定无向图 \(G=(V,E)\) 和颜色集合 \(C\)，一个合法着色是函数：

\[ \chi:V\to C \]

满足对任意边 \((u,v)\in E\)：

\[ \chi(u)\neq \chi(v) \]

\(k\)-Colorability 问题问：图 \(G\) 是否可以用不超过 \(k\) 种颜色合法着色。

当 \(k=2\) 时，问题可以多项式时间求解：

\[ G \text{ 可 2-着色} \iff G \text{ 是二分图} \iff G \text{ 不含奇环} \]

SAT 归约到 3-Colorability

3-Colorability 是 NP-complete。归约的核心构造如下：

1. 建立三个特殊顶点 \(R,G,B\)，两两相连，强制它们使用三种不同颜色
2. 对每个变量 \(x_i\)，建立两个顶点 \(x_i\) 和 \(\neg x_i\)
3. 将 \(x_i\) 和 \(\neg x_i\) 相连，并都连接到 \(B\)
4. 因为它们都不能取颜色 \(B\)，且彼此相邻，所以只能分别取 \(R\) 和 \(G\)
5. 把一种颜色解释为 TRUE，另一种解释为 FALSE
6. 对每个子句加入一个常数大小的 clause gadget，使其可 3-着色当且仅当子句中至少有一个文字为 TRUE

这样，整个图可 3-着色，当且仅当原 SAT 公式可满足。

因此：

\[ \text{SAT}\leq_p \text{3-Colorability} \]

由于 3-Colorability 属于 NP，它是 NP-complete。

3-Colorability 到 k-Colorability

上面的结论可以推广到任意固定的 \(k\geq 3\)。

当 \(k=3\) 时已经证明。若 \(k>3\)，从一个 3-Colorability 实例 \(G=(V,E)\) 出发，构造新图 \(G'\)：

1. 新增 \(k-3\) 个顶点，并让它们两两相连，形成一个大小为 \(k-3\) 的 clique
2. 将每个新增顶点都连接到原图 \(G\) 的每个顶点
3. 保留原图中的所有边

这个新增 clique 必须占用 \(k-3\) 种互不相同的颜色。由于它又和原图中每个顶点相邻，原图顶点不能使用这些颜色，只剩下 3 种颜色可用。

因此：

\[ G \text{ 可 3-着色} \iff G' \text{ 可 } k\text{-着色} \]

构造只增加 \(k-3\) 个顶点和多项式条边，所以是多项式时间归约。于是对任意固定 \(k\geq 3\)，\(k\)-Colorability 都是 NP-complete。

---

Exact Cover

Exact Cover 问题：

给定有限集合 \(X\) 和它的一族子集：

\[ \mathcal{S}=\{S_1,S_2,\ldots,S_m\} \]

问是否存在子族 \(\mathcal{S}'\subseteq\mathcal{S}\)，使得 \(X\) 中每个元素恰好出现在 \(\mathcal{S}'\) 的一个集合中。

也就是说，选出的集合两两不重叠，并且并集正好是 \(X\)。

从 3-Colorability 到 Exact Cover

课件中的构造思路是：

• 对每个图顶点 \(u\)，让 exact cover 的选择表示“给 \(u\) 选一种颜色”
• 对每条边 \((u,v)\)，加入元素和集合来禁止 \(u,v\) 选择同一种颜色
• 每个元素必须被恰好覆盖一次，因此颜色选择既不能缺失，也不能冲突

一种等价的写法如下。设颜色集合为 \(\{R,G,B\}\)。

对每个顶点 \(v\)，在全集中加入一个元素 \(a_v\)。对每条边 \(e\) 和每种颜色 \(c\)，加入一个元素 \(b_{e,c}\)。

对每个顶点 \(v\) 和颜色 \(c\)，建立集合：

\[ S_{v,c}=\{a_v\}\cup \{b_{e,c}: e \text{ incident to } v\} \]

含义是“把顶点 \(v\) 染成颜色 \(c\)”。为了覆盖没有被顶点颜色集合覆盖到的边颜色元素，再对每个 \(b_{e,c}\) 加入一个单元素集合 \(\{b_{e,c}\}\)。

如果存在 exact cover，那么每个 \(a_v\) 必须被恰好覆盖一次，所以对每个顶点 \(v\)，三个集合 \(S_{v,R},S_{v,G},S_{v,B}\) 中恰好选一个，这就给出了一个着色。

对一条边 \(e=(u,v)\)，若 \(u\) 和 \(v\) 被染成同一种颜色 \(c\)，则元素 \(b_{e,c}\) 会同时出现在 \(S_{u,c}\) 和 \(S_{v,c}\) 中，被覆盖两次，违反 exact cover。因此相邻顶点颜色不同。

反过来，若图有合法 3-着色，就选择每个顶点对应颜色的集合 \(S_{v,c}\)；对每条边，两个端点颜色不同，所以三个元素 \(b_{e,R},b_{e,G},b_{e,B}\) 中有两个已被端点集合覆盖，剩下那个用单元素集合覆盖即可。这样每个元素恰好覆盖一次。

构造规模与图的顶点数、边数成多项式关系。因此：

\[ \text{3-Colorability}\leq_p \text{Exact Cover} \]

Exact Cover 属于 NP，所以 Exact Cover 是 NP-complete。

---

整数规划

整数规划 (Integer Programming, IP) 与线性规划类似，但要求变量取整数值。

例如 Vertex Cover 可以写成 0-1 整数规划：

\[ \begin{aligned} \min\quad & \sum_{v\in V}x_v\\ \text{s.t.}\quad & x_u+x_v\geq 1,\quad \forall (u,v)\in E\\ & x_v\in\{0,1\},\quad \forall v\in V \end{aligned} \]

含义：

• \(x_v=1\) 表示选择顶点 \(v\)
• 每条边 \((u,v)\) 至少有一个端点被选中
• 目标是选最少的顶点

因为 Vertex Cover 是 NP-complete，所以一般整数规划至少是 NP-hard 的。

这也解释了为什么 LP 容易求解，而 IP 通常困难：整数约束会破坏 LP 的凸性结构。

---

Knapsack、Subset Sum 与 Partition

Knapsack

Knapsack 判定问题：

给定物品集合 \(S\)，每个物品 \(i\) 有重量 \(w_i\) 和收益 \(b_i\)，背包容量 \(W\)，目标收益 \(B\)。问是否存在 \(S'\subseteq S\)，满足：

\[ \sum_{i\in S'}w_i\leq W \]

且

\[ \sum_{i\in S'}b_i\geq B \]

0-1 背包有伪多项式 DP，但作为输入数值按二进制编码的判定问题，它是 NP-complete。

Subset Sum

Subset Sum 问题：

给定正整数集合 \(S\) 和目标 \(B\)，问是否存在 \(S'\subseteq S\)，满足：

\[ \sum_{a\in S'}a=B \]

Partition

Partition 问题：

给定正整数集合 \(S\)，问是否可以把它划分成两个和相等的子集。

令总和为：

\[ \Sigma=\sum_{a\in S}a \]

则 Partition 等价于问是否存在子集和为 \(\Sigma/2\)。

归约关系

Partition 归约到 Subset Sum

给定 Partition 输入 \(S\)，令：

\[ B=\frac{\Sigma}{2} \]

若 \(\Sigma\) 是奇数则直接为 NO；否则就是一个 Subset Sum 实例。

Subset Sum 归约到 Partition

给定 Subset Sum 输入 \((S,B)\)，令原集合总和为 \(\Sigma\)。取一个足够大的数 \(N>\Sigma\)，加入两个新元素：

\[ N-B \]

和

\[ N-(\Sigma-B) \]

新集合总和为：

\[ \Sigma+(N-B)+(N-\Sigma+B)=2N \]

因此 Partition 的目标是每边和为 \(N\)。可以证明，新集合可平分当且仅当原集合存在子集和为 \(B\)。

Partition 归约到 Knapsack

给定 Partition 输入，令：

\[ b_i=w_i,\quad W=B=\frac{\Sigma}{2} \]

则存在容量不超过 \(W\) 且收益至少 \(B\) 的背包方案，当且仅当存在子集和为 \(\Sigma/2\)。

---

伪多项式时间与弱 NP 完全

数值型问题中有一个细节：输入规模不是数值大小本身，而是编码长度。

例如整数 \(W\) 用二进制表示时，输入长度是：

\[ O(\log W) \]

而不是 \(O(W)\)。

伪多项式时间

如果一个算法的运行时间关于输入中的数值大小是多项式，但关于编码长度不一定是多项式，则称为伪多项式时间 (pseudo-polynomial time)。

0-1 背包的经典 DP：

\[ O(nW) \]

就是伪多项式时间算法。因为 \(W\) 可能是一个有 \(\log W\) 位的数，\(O(nW)\) 对输入长度来说可能是指数级。

Subset Sum 也有类似 DP：

\[ O(nB) \]

其中 \(B\) 是目标和。

弱 NP 完全

像 Subset Sum、Partition、Knapsack 这类问题是弱 NP-complete 的典型例子：

• 它们是 NP-complete
• 但存在伪多项式时间算法
• 困难性主要来自输入数字可能非常大

如果把所有数值都限制在多项式大小内，这类问题可能变得可多项式求解。

强 NP 完全

若一个问题即使在所有数值都被多项式大小限制时仍然 NP-complete，则称为强 NP-complete。

典型例子包括：

• 3SAT
• Vertex Cover
• Clique
• Hamiltonian Circuit
• 3-Dimensional Matching

强 NP-complete 问题通常不太可能存在伪多项式时间算法。更严格地说，如果一个强 NP-complete 的数值问题存在伪多项式算法，通常会推出 \(\text{P}=\text{NP}\)。

对算法设计的影响

看到数值型 NP-complete 问题时，要区分两种复杂性来源：

1. 组合结构复杂，例如 SAT、Clique、Vertex Cover
2. 数值编码导致状态空间巨大，例如 Knapsack、Subset Sum

这也是为什么背包问题虽然 NP-complete，但在很多实际场景中 DP 仍然有用。

---

Exact Cover 归约到 Subset Sum

设 Exact Cover 输入为 \((X,\mathcal{S})\)，其中：

\[ X=\{x_0,x_1,\ldots,x_{n-1}\} \]

选择一个进制 \(p\)，使得 \(p\) 大于任意元素出现的次数。对每个集合 \(A\in\mathcal{S}\)，编码成整数：

\[ N_A=\sum_{x_i\in A}p^i \]

目标数设为：

\[ B=\sum_{i=0}^{n-1}p^i \]

即在 \(p\) 进制下，每一位都是 1。

因为 \(p\) 足够大，求和时不会发生进位。因此：

• 某一位为 1 表示对应元素被覆盖一次
• 某一位为 0 表示没有被覆盖
• 某一位大于 1 表示被重复覆盖

所以存在 exact cover，当且仅当存在若干个 \(N_A\) 的和恰好为 \(B\)。

因此：

\[ \text{Exact Cover}\leq_p \text{Subset Sum} \]

这也说明 Subset Sum 是 NP-complete。

---

Bin Packing、Hamiltonian Circuit 与 TSP

Bin Packing

Bin Packing 问题：

给定物品体积 \(w_i\)、箱子容量 \(B\) 和箱子数 \(k\)，问是否能把所有物品装入不超过 \(k\) 个箱子。

Partition 可以归约到 Bin Packing：

• 令箱子数 \(k=2\)
• 令箱子容量为 \(\Sigma/2\)

能装入两个容量为 \(\Sigma/2\) 的箱子，当且仅当原集合能被平分。

Hamiltonian Circuit

Hamiltonian Circuit 问题：

给定图 \(G=(V,E)\)，问是否存在一个回路，恰好访问每个顶点一次并回到起点。

它是 NP-complete。课件中给出了从 Vertex Cover 到 Hamiltonian Circuit 的 gadget 构造：用顶点 gadget 和额外节点迫使 Hamiltonian 回路的走法对应一个大小受限的顶点覆盖。

TSP

TSP 判定问题：

给定带非负边权的图和整数 \(K\)，问是否存在一条总权重不超过 \(K\) 的回路，恰好访问每个顶点一次并回到起点。

Hamiltonian Circuit 可以归约到 TSP：

给定无权图 \(G=(V,E)\)，构造同一顶点集上的完全图 \(G'\)：

\[ w(u,v)= \begin{cases} 1 & (u,v)\in E\\ 2 & (u,v)\notin E \end{cases} \]

令：

\[ K=|V| \]

若原图有 Hamiltonian circuit，则在 \(G'\) 中存在长度为 \(|V|\) 的 TSP tour。反过来，若 \(G'\) 中存在长度不超过 \(|V|\) 的 tour，由于每条边权至少为 1，tour 必须全部使用权重为 1 的边，因此对应原图中的 Hamiltonian circuit。

所以：

\[ \text{Hamiltonian Circuit}\leq_p \text{TSP} \]

TSP 属于 NP，因此 TSP 是 NP-complete。

---

困难问题的分类

课件中给出了一些常见 NP-hard/NP-complete 问题的类型：

类型	代表问题
Packing	Independent Set、Set Packing
Covering	Vertex Cover、Set Cover
Partitioning	Graph Coloring、3-Dimensional Matching
Sequencing	Hamiltonian Cycle、TSP
Numerical	Subset Sum、Partition、Knapsack
Constraint Satisfaction	SAT、3-SAT

这些问题表面上来自图论、组合优化、数值问题和逻辑公式，但通过多项式时间归约，它们被放进了同一个困难性框架中。

---

证明 NP-complete 的常见错误

NP-complete 证明最容易错在归约方向和问题版本上。

归约方向写反

要证明新问题 \(B\) 是 NP-hard，应该证明：

\[ A\leq_p B \]

其中 \(A\) 是已知 NP-hard 或 NP-complete 的问题。

错误方向：

\[ B\leq_p A \]

只能说明 \(B\) 不比 \(A\) 难，不能说明 \(B\) 很难。

只证明了单向蕴含

归约必须保证：

\[ x\in A\iff f(x)\in B \]

只证明 YES 映射到 YES 不够；还要证明 NO 映射到 NO，或者等价地证明反向蕴含。

忘记证明属于 NP

NP-hard 不等于 NP-complete。要证明 NP-complete，还必须说明该问题属于 NP，也就是 YES 实例有多项式大小证书并可多项式时间验证。

把优化问题和判定问题混用

NP-complete 是判定问题的概念。若原问题是优化问题，通常要先写出判定版本。例如：

• “最小顶点覆盖大小是多少”是优化问题
• “是否存在大小不超过 \(K\) 的顶点覆盖”是判定问题

构造规模不是多项式

归约函数 \(f\) 必须在多项式时间内构造输出实例，输出规模也必须是输入规模的多项式。

如果构造中隐含枚举指数多个对象，例如所有路径、所有子集、所有赋值，就不能直接作为多项式归约。

---

小结

NP 完全性的核心逻辑是：

1. NP 中的问题有多项式大小证书，并且证书可多项式时间验证
2. 多项式时间归约表示“会解后者就会解前者”
3. SAT 由 Cook 定理成为第一个 NP-complete 问题
4. 通过归约链可以证明大量自然问题都是 NP-complete
5. co-NP 强调 NO 证书，伪多项式时间解释了背包、子集和等数值型问题的特殊性

本节主要归约链包括：

\[ \text{SAT} \leq_p \text{Clique} \leq_p \text{Independent Set} \leq_p \text{Vertex Cover} \]

也可以使用：

\[ \text{3SAT} \leq_p \text{Independent Set} \leq_p \text{Vertex Cover} \]

以及：

\[ \text{SAT} \leq_p \text{Exact-3SAT} \]

\[ \text{SAT} \leq_p \text{3-Colorability} \leq_p k\text{-Colorability}\quad(k\geq 3) \leq_p \text{Exact Cover} \leq_p \text{Subset Sum} \]

\[ \text{Partition} \leq_p \text{Knapsack},\quad \text{Partition} \leq_p \text{Bin Packing} \]

\[ \text{Hamiltonian Circuit} \leq_p \text{TSP} \]

证明一个问题 NP-complete 后，并不等于证明它没有多项式时间算法；它说明的是：如果这个问题有多项式时间算法，那么整个 NP 都有多项式时间算法，也就是 \(\text{P}=\text{NP}\)。在当前理论背景下，这通常被视为强烈的困难性证据。