第 34 章 NP 完全性

本章对应原书第 34 章。前面各章的算法几乎都是多项式时间的。可是量化里很多看似普通的问题——"从 300 只股票里恰好选 30 只跟踪指数""按整手买入、恰好花完预算""在资金约束下选一批交易机会使预期收益最大"——却没有人找到多项式时间的精确算法，而且很可能永远找不到。NP 完全性理论给了我们识别这类问题的工具：它不告诉你怎么解，而是告诉你别再找快速精确算法了，该转向小规模精确求解、特殊结构或近似算法（第 35 章）。本章讲清 P、NP、NPC 的含义，归约的思想和方向，经典的归约链，以及如何判断自己手上的组合优化问题是不是 NP 难的。电路构造、部件（widget）等证明细节只保留思路。

学习目标

读完本章，你应当能够：

1. 用"可多项式时间求解"与"可多项式时间验证"区分 P 与 NP，说清证书（certificate）的含义，以及为什么 P ⊆ NP。
2. 解释判定问题与优化问题的关系，以及编码方式为什么重要——尤其是"伪多项式时间"：背包、子集和的 \(O(nt)\) 动态规划为什么不算多项式时间。
3. 正确使用多项式时间归约 \(L_1\le_P L_2\)，记住方向：从已知难问题归约到新问题才能证明新问题难。
4. 复述经典归约链 CIRCUIT-SAT → SAT → 3-CNF-SAT → CLIQUE → VERTEX-COVER → HAM-CYCLE → TSP，以及 3-CNF-SAT → SUBSET-SUM，并能讲出每一步的构造思想。
5. 判断带基数约束、整手约束、0-1 选择的组合构建问题属于 NP 难问题，并知道实践中的应对办法。

读前导读

这一章在解决什么问题

这一章不教你怎么解问题，而是教你识别哪些问题没有快速的精确解法，从而及时换思路。

先看一个你熟悉的对比。连续权重的均值–方差优化，用二次规划求解器几秒就有精确最优解，股票再多也不怕。可是只要加一条"最多持有 30 只股票"，或者"必须按整手买、恰好花完预算"，问题就变了性质：可能的持仓组合数从 300 只里选 30 只，约有 \(10^{41}\) 种，求解时间会随规模爆炸式增长。这不是求解器不够好，而是问题本身属于一类公认的"难题"——NP 难问题。

NP 完全性理论的核心思想只有两条，都可以用金融语言理解：

• 求解难，但验证容易。 有人交给你一个"恰好花完预算"的买入清单，你加一加就知道对不对；但要自己找出这样一个清单，可能要试遍所有组合。这类"答案容易核对"的问题统称 NP。这和审计很像：核对一张已编好的报表容易，从原始凭证编出一张报表难。
• 归约就是"转化为已知问题"。 如果能把一个公认的难题改写成你的问题，那么你的问题至少一样难——否则用你的问题的快速解法就能顺带解决那个难题。这和无套利定价里"能被复制的东西，价格必须一致"是同一种论证方式：通过"如果……就能……"推出矛盾。

对量化工作的实际意义是：一旦判断出手上的组合构建问题是 NP 难的，就不要再期待"更聪明的精确算法"，而应该转向小规模精确求解（混合整数规划求解器）、利用特殊结构（例如金额离散化后的动态规划），或者有质量保证的近似算法（第 35 章）。

需要先想起来的数学

1. 多项式增长与指数增长。 \(n^2\)、\(n^3\) 是多项式增长：规模翻倍，时间变成 4 倍、8 倍。\(2^n\)、\(n!\) 是指数增长：规模加 1，时间就翻倍。\(n=60\) 时 \(n^3=216{,}000\)，而 \(2^{60}\approx10^{18}\)。本章说的"易处理"就是多项式时间，"难处理"就是超多项式时间。\(O(\cdot)\)、\(\Omega(\cdot)\)、\(\Theta(\cdot)\) 分别表示上界、下界、同阶，见本册 第 03 章 函数的增长与渐近记号。

2. 布尔逻辑。 变量只取真（1）或假（0）。\(\wedge\) 是"且"，\(\vee\) 是"或"，\(\neg\) 是"非"，\(\leftrightarrow\) 是"当且仅当"。例如 \((x_1\vee\neg x_2)\) 在 \(x_1\) 为真或 \(x_2\) 为假时成立。"可满足"是指存在一组取值让整个公式为真。

3. 读证明的逻辑。 "\(A\iff B\)"要两个方向都证；"若 \(A\) 则 \(B\)"的逆否命题"若非 \(B\) 则非 \(A\)"与原命题等价，归约证明大量使用这种推理。见 第 00 册第 08 章 读懂数学证明与符号。

怎么读这一章

核心必读：34.1（P、NP、NPC 的直观含义）、34.2.2（伪多项式时间）、34.5.1 的"常见误区：方向"、34.6（量化实战）。读完这几节，你就能判断自己的问题是否属于难题、该怎么应对。

第一次可以跳过：34.2.3 形式语言框架、34.3.3 co-NP、34.4.3 电路可满足性的证明草图，以及 34.5.2–34.5.6 各个归约的构造细节（团、顶点覆盖、哈密顿回路）。这些是理论计算机科学的标准内容，对使用者来说只需记住结论："这些问题都是 NP 完全的"。34.5.7 子集和值得一读，因为"整手买入恰好花完预算"就是子集和问题。

34.1 为什么研究"难"问题

34.1.1 易处理与难处理

多项式时间算法：规模为 \(n\) 的输入上，最坏运行时间为 \(O(n^k)\)（\(k\) 为常数）。一般把多项式时间可解的问题称为易处理的（tractable），需要超多项式时间的称为难处理的（intractable）。并非所有问题都能解：图灵的停机问题（Halting Problem）任何计算机都无法判定；也有问题可解，但不可能在任何 \(O(n^k)\) 时间内解决。

本章研究一类状态未知的问题——NP 完全（NP-complete）问题：至今没有人找到其中任何一个的多项式时间算法，也没有人证明它们不存在多项式时间算法。这就是 1971 年提出以来理论计算机科学最深刻的开放问题：P ≠ NP？

34.1.2 表面相似、难度悬殊的问题对

原书用三对例子说明，问题的难度常常和直觉不符：

• 最短 vs. 最长简单路径：即使有负权边，单源最短路也能 \(O(VE)\) 求出；但仅判断"是否存在至少含 \(k\) 条边的简单路径"就是 NP 完全的。
• 欧拉回路 vs. 哈密顿回路：经过每条边恰好一次的欧拉回路可在 \(O(E)\) 内判定并求出；经过每个顶点恰好一次的哈密顿回路的判定是 NP 完全的。
• 2-CNF vs. 3-CNF 可满足性：每个子句两个文字的布尔公式可在多项式时间判定是否可满足（习题 34.4-7：蕴含图加强连通分量，线性时间）；每个子句三个文字就是 NP 完全的。

量化里也有同样的现象：连续权重的均值–方差优化是凸二次规划，多项式时间可解；加上一条"最多持有 30 只股票"，问题就变成 NP 难。

34.1.3 P、NP、NPC 的直观含义

• P：多项式时间可求解的问题。
• NP：多项式时间可验证的问题——如果有人给出一个解（证书，certificate），你能在多项式时间内检查它是否正确。例如哈密顿回路的证书是顶点序列，检查相邻顶点之间是否都有边即可；3-CNF 可满足性的证书是一组变量赋值，代入求值即可。P ⊆ NP，因为能求解就不需要证书。
• NPC：属于 NP，而且与 NP 中任何问题"一样难"。若任何一个 NP 完全问题有多项式算法，NP 中所有问题都有多项式算法。

大多数理论计算机科学家相信 NP 完全问题是难处理的：这么多被深入研究的 NP 完全问题无一找到多项式算法，若它们全部可解将令人震惊。但这也没有被证明。

实践意义：如果你能证明一个问题是 NP 完全的，就有了它难处理的有力证据。这时更好的做法是设计近似算法、求解有实际意义的特殊情形，或接受指数时间的精确算法用于小规模实例，而不是继续寻找快速精确算法。

34.2 形式化：判定问题、编码与类 P

34.2.1 判定问题与优化问题

优化问题（optimization problem）要在可行解中找值最优的那个。例如 SHORTEST-PATH：给定无向图 \(G\) 和顶点 \(u,v\)，求边数最少的 \(u\)–\(v\) 路径。NP 完全性只直接适用于判定问题（decision problem）——答案只有"是/否"。给优化目标加一个界就得到判定版本，例如 PATH：是否存在至多 \(k\) 条边的 \(u\)–\(v\) 路径？

判定问题不比对应的优化问题难：能求出最短路径，就能回答 PATH。所以，证明了判定版本难，就证明了优化版本难。反过来，判定版本的黑盒通常也能在多项式次调用内求出最优值（二分 \(k\)）乃至最优解（习题 34.4-6 的自归约：逐个固定变量，每次问黑盒"固定之后还能满足吗"）。

34.2.2 编码与伪多项式时间

算法处理的是实例的编码（encoding）——把抽象对象映射成二进制串。运行时间要按编码长度衡量，而效率强烈依赖编码方式。原书的例子：设算法唯一的输入是整数 \(k\)，运行时间 \(\Theta(k)\)。

• 若 \(k\) 用一元编码（\(k\) 个 1），输入长度 \(n=k\)，运行时间 \(O(n)\)，是多项式；
• 若用二进制，输入长度 \(n=\lfloor\lg k\rfloor+1\)，运行时间 \(\Theta(k)=\Theta(2^n)\)，是指数。

这就是伪多项式时间（pseudo-polynomial time）的来源。0-1 背包的动态规划 \(O(nW)\)、子集和的动态规划 \(O(nt)\)，看起来是多项式，但 \(W\)、\(t\) 是数值而不是长度：多写一位数字，运行时间就乘以 10（习题 34.1-4）。排除一元编码这种"浪费"的编码后，二进制、三进制等合理编码之间可多项式时间互转，不影响问题是否在 P 中（引理 34.1）。此后默认使用合理、简洁的编码，记作 \(\langle G\rangle\) 等。

对量化来说，伪多项式是个好消息：若金额以"最小变动单位""一手"离散化后数值不大，\(O(nt)\) 的动态规划完全可用。34.6.5 节会演示它的代价如何随数字位数指数增长。

白话解释：为什么 \(O(nt)\) 不算"多项式"？关键在于衡量"输入有多大"的尺子。把预算 \(t\) 写下来只需要它的位数：100 万元以分计是 \(10^8\)，只要写 9 位数字；但 \(O(nt)\) 的动态规划要为 \(0,1,2,\dots,t\) 每一个金额都建一个格子，也就是 \(10^8\) 个。输入只多写一位数字，格子数就乘以 10，所以相对于"输入长度"它是指数增长的。

实务上的含义很直接：同一个"整手买入凑预算"问题，金额以"万元"为单位离散化时 \(t\) 很小，动态规划瞬间完成；以"分"为单位时 \(t\) 大一百万倍，可能就算不动了。精度要求决定了这个问题在实际中难不难。

34.2.3 形式语言框架与类 P

为了严格定义，原书把判定问题写成语言：字母表 \(\Sigma=\{0,1\}\) 上回答为"是"的实例构成的串集合，例如

把多项式时间当作"易处理"的理由是哲学性的而非数学的：实际中很少有问题需要 \(n^{100}\) 这样高次的多项式，一旦找到多项式算法往往很快就有更好的；多项式可解性在各种合理计算模型（RAM、图灵机、多项式个处理器的并行机）之间不变；多项式在加、乘、复合下封闭，多项式算法调用常数次多项式子程序仍是多项式（习题 34.1-5）。

34.3 多项式时间验证与类 NP

34.3.1 哈密顿回路

无向图中包含每个顶点的简单回路称为哈密顿回路（hamiltonian cycle）。判定问题

但如果朋友声称图是哈密顿的，并给出回路上的顶点顺序，检查起来很容易：确认序列是顶点的一个排列，相邻（含首尾）顶点之间都有边，\(O(n^2)\) 时间。

34.3.2 验证算法与 NP 的定义

验证算法（verification algorithm）\(A(x,y)\) 有两个输入：普通输入 \(x\) 和证书 \(y\)。\(A\) 验证的语言是

定义（类 NP） \(L\in\mathrm{NP}\) 当且仅当存在两输入的多项式时间算法 \(A\) 和常数 \(c\)，使

HAM-CYCLE ∈ NP。P ⊆ NP：多项式判定算法可改写成忽略证书的验证算法。

直观上，P 是能被快速求解的问题，NP 是解能被快速验证的问题。经验上，从零构造一个解往往比检查一个现成的解难得多——这就是多数人相信 P ≠ NP 的直觉来源。

34.3.3 co-NP 与未解之谜

我们甚至不知道 NP 是否对补运算封闭。定义 \(\text{co-NP}=\{L:\bar L\in\mathrm{NP}\}\)。例如"公式对所有赋值都为真"（TAUTOLOGY）在 co-NP 中：一个反例赋值就能证明它不是永真式（习题 34.2-8）。已知 \(\mathrm P\subseteq\mathrm{NP}\cap\text{co-NP}\)。原书图 34.3 画出四种可能：(a) P = NP = co-NP（多数人认为最不可能）；(b) NP = co-NP 但 P ≠ NP；(c) P = NP ∩ co-NP 但 NP ≠ co-NP；(d) NP ≠ co-NP 且 P ≠ NP ∩ co-NP（多数人认为最可能）。我们对 P 与 NP 关系的理解极不完整。

34.4 归约与 NP 完全性

34.4.1 多项式时间归约

直观上，若问题 \(Q\) 的任何实例都能"容易地改写"成 \(Q'\) 的实例，而后者的答案就是前者的答案，那么 \(Q\) 不比 \(Q'\) 难。例：一元线性方程 \(ax+b=0\) 可改写为二次方程 \(0x^2+ax+b=0\)。

定义 语言 \(L_1\) 多项式时间可归约（polynomial-time reducible）到 \(L_2\)，记 \(L_1\le_PL_2\)，若存在多项式时间可计算函数 \(f\)，使对所有 \(x\)，

引理 34.3 若 \(L_1\le_PL_2\) 且 \(L_2\in\mathrm P\)，则 \(L_1\in\mathrm P\)。

证明：判定 \(x\in L_1\)：先算 \(f(x)\)，再用 \(L_2\) 的多项式算法判定 \(f(x)\)。若 \(f\) 需 \(O(n^c)\)，则 \(|f(x)|=O(n^c)\)，第二步需 \(O(n^{ck})\)，总时间仍是多项式。\(\square\)

"\(\le\)"记号便于记忆：\(L_1\le_PL_2\) 表示 \(L_1\) 至多比 \(L_2\) 难一个多项式因子。

金融直觉：归约和复制定价的逻辑相同。在衍生品里，如果期权 \(X\) 能用股票和债券复制出来，那么 \(X\) 的定价问题"不比"股票和债券的定价问题难：知道后者，前者就确定了。\(L_1\le_PL_2\) 说的是同一件事：\(L_1\) 的任何实例都能被快速"翻译"成 \(L_2\) 的实例，并且答案不变，所以只要有解 \(L_2\) 的快速方法，就能快速解 \(L_1\)。

式 (34.1) 中的 \(\iff\) 很重要：翻译必须保证"是"的实例翻译后仍为"是"，"否"的实例翻译后仍为"否"。只保证一个方向，翻译后的答案就不可信。

34.4.2 NP 完全与 NP 难

定义 语言 \(L\) 是 NP 完全的（\(L\in\mathrm{NPC}\)），若

1. \(L\in\mathrm{NP}\)；
2. 对每个 \(L'\in\mathrm{NP}\)，\(L'\le_PL\)。

只满足第 2 条的称为 NP 难（NP-hard）。优化问题不是语言，严格说只能是 NP 难的；本书和实务中常说"某优化问题 NP 难"，意思是它的判定版本 NP 完全。

定理 34.4 若任何一个 NP 完全问题多项式时间可解，则 P = NP。等价地，若 NP 中有任何问题不能多项式求解，则所有 NP 完全问题都不能。

证明：设 \(L\in\mathrm P\cap\mathrm{NPC}\)。对任意 \(L'\in\mathrm{NP}\)，\(L'\le_PL\)，由引理 34.3，\(L'\in\mathrm P\)。\(\square\)

多数人相信的图景（原书图 34.6）：P 与 NPC 都在 NP 内，且 \(\mathrm P\cap\mathrm{NPC}=\emptyset\)。

34.4.3 第一个 NP 完全问题：电路可满足性

归约需要一个已知 NP 完全的起点。原书用电路可满足性：由 AND、OR、NOT 门组成的单输出布尔组合电路（无环），是否存在一组输入使输出为 1？

引理 34.5 CIRCUIT-SAT ∈ NP。证书是电路中每根导线的取值，逐个门检查输出是否等于门函数作用于输入、整体输出是否为 1，线性时间。

引理 34.6 CIRCUIT-SAT 是 NP 难的。证明思路（原书称为"草图"）：

• 设 \(L\in\mathrm{NP}\)，有多项式时间验证算法 \(A\)，运行时间 \(T(n)=O(n^k)\)。
• 计算机执行程序时，内存的整体状态（程序、程序计数器、输入、证书、工作存储）称为一个格局（configuration）。执行一条指令就是把一个格局映射为下一个，实现这个映射的硬件是一个布尔组合电路 \(M\)。
• 把 \(T(n)\) 个 \(M\) 首尾串联，格局"活在导线上"。把程序、输入 \(x\)、初始状态对应的输入端接成常数，只留证书 \(y\) 对应的输入端自由，输出端只取最终格局中代表 \(A\) 输出的那一位。得到的电路 \(C=f(x)\) 满足 \(C(y)=A(x,y)\)。
• 于是 \(x\in L\iff\) 存在 \(y\) 使 \(A(x,y)=1\iff C\) 可满足。格局长度和电路规模都是 \(n\) 的多项式，构造是多项式时间。

定理 34.7 CIRCUIT-SAT 是 NP 完全的。这是 Cook–Levin 定理的电路版本。

34.5 NP 完全性证明：经典归约链

34.5.1 标准方法

引理 34.8 若存在 \(L'\in\mathrm{NPC}\) 使 \(L'\le_PL\)，则 \(L\) 是 NP 难的；若再有 \(L\in\mathrm{NP}\)，则 \(L\in\mathrm{NPC}\)。（由 \(\le_P\) 的传递性。）

证明一个语言 \(L\) 是 NP 完全的五步法：

1. 证明 \(L\in\mathrm{NP}\)；
2. 选一个已知 NP 完全的语言 \(L'\)；
3. 给出把 \(L'\) 的实例 \(x\) 映射为 \(L\) 的实例 \(f(x)\) 的算法；
4. 证明 \(x\in L'\iff f(x)\in L\)（双向都要证）；
5. 证明这个算法是多项式时间的。

常见误区：方向。要证明新问题 \(L\) 难，必须把已知难题归约到 \(L\)（\(L'\le_PL\)）——"如果 \(L\) 容易，那么已知难题也容易，矛盾"。把 \(L\) 归约到一个已知难题，只说明 \(L\) 不比它难，什么也证明不了。另外两个方法论要点（原书 34.5.1 节）：归约只能用实例本身，不能用实例的解；只需在已知难题的全部实例上成立，构造出的目标实例可以是特殊结构的——特殊结构上都难，一般情形自然更难。

白话解释：方向之所以容易搞反，是因为直觉上"把我的问题转化成已知问题"更自然——那确实是解决问题的思路（例如把指数跟踪写成 LP，再交给 LP 求解器）。但要证明一个问题难，逻辑是反的：要说明"如果你的问题有快速解法，那么子集和（公认的难题）也有快速解法"，所以必须展示怎样把任意一个子集和实例改写成你的问题。

以 34.6.1 节的"整手买入恰好花完预算"为例：给定任意子集和实例（一组正整数和目标 \(t\)），把每个整数当作一只股票一手的金额、把 \(t\) 当作预算，就得到一个整手买入问题，而且两者答案相同。所以整手买入问题至少和子集和一样难。注意这里构造出的只是"每只股票至多一手"的特殊情形，但正如原文所说，特殊情形已经难，一般情形自然也难。

原书的归约结构（图 34.13）：

34.5.2 公式可满足性 SAT

SAT 的实例是由变量、联结词（∧、∨、¬、→、↔ 等）和括号组成的布尔公式，问是否存在满足赋值。它是历史上第一个被证明 NP 完全的问题（Cook，1971）。

定理 34.9 SAT 是 NP 完全的。

• ∈ NP：证书是满足赋值，代入求值。
• CIRCUIT-SAT \(\le_P\) SAT：朴素地从输出门开始递归展开成公式不行——扇出 ≥ 2 的导线会让共享的子公式被反复复制，规模可能指数膨胀（习题 34.4-1）。正确做法是给每根导线一个变量，每个门写成一个"\(\leftrightarrow\)"小子句，如 \(x_{10}\leftrightarrow(x_7\wedge x_8\wedge x_9)\)，最后把输出变量与所有门子句取合取。规模线性。

"为中间量引入新变量以避免指数膨胀"是贯穿后面所有归约的基本技巧。

34.5.3 3-CNF 可满足性

文字（literal）是变量或其否定；合取范式（CNF）是若干子句的合取，每个子句是文字的析取；3-CNF 要求每个子句恰好三个不同文字。从受限的问题出发归约，要考虑的情形少，但不能限制得过头（2-CNF-SAT、DNF-SAT 都在 P 中）。

定理 34.10 3-CNF-SAT 是 NP 完全的。SAT \(\le_P\) 3-CNF-SAT 分三步：

1. 语法树 + 新变量：为公式建二叉语法树，每个内部结点引入变量 \(y_i\)，公式改写为"根变量 ∧ 各结点子句 \(y_i\leftrightarrow(\cdot)\)"，每个子句至多 3 个文字。
2. 每个子句转 CNF：列出至多 8 行的真值表，用取值为 0 的行写出 \(\neg\phi'_i\) 的析取范式，再用 De Morgan 律取反得到 CNF。
3. 补足到恰好 3 个文字：用两个辅助变量 \(p,q\)。两个文字的子句 \((l_1\vee l_2)\) 换成 \((l_1\vee l_2\vee p)\wedge(l_1\vee l_2\vee\neg p)\)；一个文字的子句用 \(p,q\) 的四种组合换成四个子句。无论 \(p,q\) 取何值，结果与原子句等价。

每一步规模都只增加常数倍，归约是多项式的。

34.5.4 团问题

无向图中的团（clique）是两两相邻的顶点子集。\(\text{CLIQUE}=\{\langle G,k\rangle:G\text{ 含规模为 }k\text{ 的团}\}\)。

定理 34.11 CLIQUE 是 NP 完全的。归约 3-CNF-SAT \(\le_P\) CLIQUE：设公式有 \(k\) 个子句。每个子句的三个文字各对应一个顶点（一个"三元组"）；两个顶点之间连边，当且仅当它们来自不同子句、且两个文字不矛盾（不是 \(x\) 与 \(\neg x\)）。

• 公式可满足 ⇒ 每个子句选一个真文字，这 \(k\) 个顶点两两来自不同子句、都为真因而不矛盾，构成 \(k\)-团；
• 有 \(k\)-团 ⇒ 同一子句内的顶点之间无边，所以团恰好在每个子句中取一个顶点；把这些文字设为真不会冲突（矛盾文字间无边），每个子句都被满足。

34.5.5 顶点覆盖

顶点覆盖（vertex cover）是一个顶点子集，使每条边至少有一个端点在其中。

定理 34.12 VERTEX-COVER 是 NP 完全的。归约 CLIQUE \(\le_P\) VERTEX-COVER 用补图 \(\bar G\)：\(V'\) 是 \(G\) 的团，当且仅当 \(V-V'\) 是 \(\bar G\) 的顶点覆盖。所以把 \(\langle G,k\rangle\) 映射为 \(\langle\bar G,|V|-k\rangle\)。证明：\(\bar G\) 的边 \((u,v)\) 不在 \(G\) 中，\(u,v\) 不能同在团 \(V'\) 里，所以至少一个在 \(V-V'\) 中；反之亦然。

原书特别提醒：顶点覆盖虽然 NP 完全，但第 35 章有简单的多项式时间 2-近似算法——NP 完全不等于放弃。

34.5.6 哈密顿回路与旅行商

定理 34.13 HAM-CYCLE 是 NP 完全的。归约 VERTEX-COVER \(\le_P\) HAM-CYCLE 是本章最精巧的构造：为每条边 \((u,v)\) 造一个 12 个顶点的部件（widget），它只能以三种方式被哈密顿回路穿过，分别对应"边被 \(u\) 覆盖""被 \(v\) 覆盖""被两者覆盖"；再加 \(k\) 个选择顶点，回路每经过一个选择顶点就"选中"一个覆盖顶点，并走遍与它关联的所有部件。\(G\) 有规模 \(k\) 的顶点覆盖当且仅当新图有哈密顿回路。细节见原书 p.1112–1117。

旅行商问题（TSP）：完全图上有非负整数代价，求总代价最小的巡回。判定版本问是否有代价 \(\le k\) 的巡回。

定理 34.14 TSP 是 NP 完全的。归约 HAM-CYCLE \(\le_P\) TSP：原图中的边代价为 0，非边代价为 1，问是否有代价 \(\le0\) 的巡回。代价为 0 的巡回只能全用原图的边，就是哈密顿回路。

34.5.7 子集和

给定正整数集合 \(S\) 和目标 \(t\)，问是否有子集之和恰为 \(t\)。原书例：\(S=\{1,2,7,14,49,98,343,686,2409,2793,16808,17206,117705,117993\}\)，\(t=138457\)，解为 \(\{1,2,7,98,343,686,2409,17206,117705\}\)。

关键前提：整数用二进制编码。若 \(t\) 用一进制表示，\(O(nt)\) 的动态规划就是多项式时间（习题 34.5-4）。

定理 34.15 SUBSET-SUM 是 NP 完全的。归约 3-CNF-SAT \(\le_P\) SUBSET-SUM：设公式有 \(n\) 个变量、\(k\) 个子句（假设没有子句同时含 \(x_i\) 与 \(\neg x_i\)、每个变量至少出现一次）。构造一批 \(n+k\) 位的十进制数，高 \(n\) 位对应变量，低 \(k\) 位对应子句：

• 目标 \(t\)：变量位全为 1，子句位全为 4；
• 每个变量 \(x_i\) 造两个数 \(v_i\)、\(v'_i\)：\(x_i\) 位为 1；若 \(x_i\) 出现在 \(C_j\) 中，\(v_i\) 的 \(C_j\) 位为 1；若 \(\neg x_i\) 出现在 \(C_j\) 中，\(v'_i\) 的 \(C_j\) 位为 1；
• 每个子句 \(C_j\) 造两个松弛数 \(s_j=1\)、\(s'_j=2\)（只在 \(C_j\) 位）。

任一位上的数字和至多为 6（三个文字的 1，加上 1+2），十进制下不会进位，所以各位可以独立看：

• 变量位要等于 1 ⇒ 对每个 \(i\) 恰好选 \(v_i\) 或 \(v'_i\) 之一——这就是一组赋值；
• 子句位要等于 4，而松弛数至多贡献 3 ⇒ 至少有一个被选中的 \(v\) 在该子句位为 1，即该子句至少有一个真文字。

推导拆解：这个构造的巧妙之处是把"逻辑条件"变成"按位记账"。可以把每一位想成一个独立的科目，把目标 \(t\) 想成各科目必须对上的余额。

变量科目：每个 \(x_i\) 的科目余额必须是 1，而只有 \(v_i\)、\(v'_i\) 在这一位上有 1，所以二者必须恰好选一个。选 \(v_i\) 表示"\(x_i\) 为真"，选 \(v'_i\) 表示"\(x_i\) 为假"。

子句科目：每个子句的余额必须是 4。被选中的文字数在这一位上贡献 0 到 3，松弛数 \(s_j=1\)、\(s'_j=2\) 能补上 0、1、2 或 3。若该子句没有任何真文字，文字贡献为 0，松弛数最多补 3，凑不到 4；若有 1 到 3 个真文字，总能用松弛数补齐到 4。所以"能凑出 \(t\)"恰好等价于"每个子句至少有一个真文字"，即公式可满足。

用十进制且保证每位之和不超过 6，是为了防止进位把不同科目搅在一起——就像各科目分别记账，不允许串户。

原书图 34.19 的例子：\(C_1=(x_1\vee\neg x_2\vee\neg x_3)\)，\(C_2=(\neg x_1\vee\neg x_2\vee\neg x_3)\)，\(C_3=(\neg x_1\vee\neg x_2\vee x_3)\)，\(C_4=(x_1\vee x_2\vee x_3)\)，构造出

34.5.8 更多 NP 完全问题

习题和思考题给出一批常见的 NP 完全问题，量化中能遇到的形式加了说明：

• 0-1 整数规划（习题 34.5-2）：给定整数矩阵 \(A\) 和向量 \(b\)，是否存在 \(x\in\{0,1\}^n\) 使 \(Ax\le b\)；一般整数线性规划也 NP 完全（34.5-3）。几乎所有带离散决策的组合构建问题都能写成它。
• 集合划分（34.5-5）：能否把整数集分成和相等的两半。思考题 34-2 的"分赃"问题：两种面值的硬币或面值都是 2 的幂时有多项式算法，任意金额的支票就是集合划分，NP 完全。
• 独立集（思考题 34-1）：\(G\) 的独立集就是 \(\bar G\) 的团，NP 完全；但在二部图上可用最大匹配多项式求解，度为 2 的图上也容易——特殊结构常常让难题变易。
• 图着色（思考题 34-3）：2-着色就是判断二部图，BFS 即可；3-着色 NP 完全。
• 带利润与截止期的单机调度（思考题 34-4）：NP 完全（可从子集和归约），但加工时间是小整数时可用动态规划。
• 子图同构（34.5-1）、哈密顿路径（34.5-6）、最长简单回路（34.5-7）等。

章末注记：Garey 与 Johnson 的《Computers and Intractability》（1979）是 NP 完全问题的经典目录；P 类由 Cobham 和 Edmonds 独立提出；Cook（1971）证明 SAT 与 3-CNF-SAT 的 NP 完全性，Levin 独立发现；Karp（1972）用归约证明了团、顶点覆盖、哈密顿回路等 21 个问题的 NP 完全性。近年的 PCP 理论表明，许多问题连求好的近似解也是 NP 难的。

34.6 量化实战：识别并应对 NP 难的组合问题

34.6.1 哪些组合构建问题是 NP 难的

先说哪些不是：连续权重、凸目标、线性约束的组合优化——均值–方差、最小跟踪误差（不限持仓数）、带线性换手约束的再平衡——都是凸二次规划，多项式时间可解（第 04 册第 16a、16b 章）。

一旦引入离散决策，问题通常就变成 NP 难：

• 整手与恰好用完预算。\(n\) 只股票，第 \(i\) 只一手的金额为 \(p_i\)（整数，以分计），每只至多买一手，能否恰好花掉预算 \(t\)？这就是 SUBSET-SUM，NP 完全。允许买多手、目标改为"不超预算的最大花费"，就是 0-1 背包的变体，NP 难。
• 基数约束。"至多/恰好持有 \(K\) 只股票"使问题含有 \(\binom NK\) 种支撑集选择。以最小跟踪误差为目标时，它和统计中的最优子集选择（稀疏最小二乘）同类，后者已被证明是 NP 难的（Natarajan，1995）。
• 最小交易单位与最小持仓："要么不持有，要么至少持有 1%"这类半连续约束，需要 0-1 变量表达，是 0-1 整数规划。
• 选择交易机会：每个机会占用资金、有预期收益，资金有限——0-1 背包。

34.6.2 应对策略

原书第 35 章开头列出的三条路，正好对应实践中的三类做法：

1. 规模小或结构好时精确求解：混合整数二次规划（MIQP）求解器（Gurobi、CPLEX、SCIP 等）用分支定界，几十到几百只股票的基数约束问题常能在可接受时间内求到最优或证明间隙很小。
2. 利用特殊结构：金额离散化后数值不大时用伪多项式 DP；约束矩阵全单模时 LP 松弛自动给出整数解。
3. 近似与启发式：贪心（前向选择、逐步剔除）、连续松弛后舍入（如先解无基数约束的问题，再保留权重最大的 \(K\) 只并重新优化）、局部搜索。第 35 章讨论哪些启发式有可证明的保证。

34.6.3 代码一：用代码复现子集和归约

把原书图 34.19 的构造写成程序，用动态规划求出凑成 \(t\) 的子集，再从子集中读出满足赋值。

import itertools

# 原书图 34.19 的 3-CNF 公式：文字用 (变量号, 是否取反)
clauses = [[(1, False), (2, True), (3, True)],     # C1 = x1 ∨ ¬x2 ∨ ¬x3
           [(1, True), (2, True), (3, True)],      # C2 = ¬x1 ∨ ¬x2 ∨ ¬x3
           [(1, True), (2, True), (3, False)],     # C3 = ¬x1 ∨ ¬x2 ∨ x3
           [(1, False), (2, False), (3, False)]]   # C4 = x1 ∨ x2 ∨ x3
n, k = 3, len(clauses)

def reduce_3cnf_to_subset_sum(clauses, n):
    """定理 34.15 的归约：每个数 n+k 位十进制，高 n 位对应变量，低 k 位对应子句"""
    k = len(clauses)
    digit = lambda pos: 10 ** (n + k - 1 - pos)           # 第 pos 位（从左数，0 起）
    S = {}
    for i in range(1, n + 1):
        v = vp = digit(i - 1)
        for j, C in enumerate(clauses):
            if (i, False) in C: v += digit(n + j)
            if (i, True) in C:  vp += digit(n + j)
        S[f"v{i}"], S[f"v{i}'"] = v, vp
    for j in range(k):
        S[f"s{j+1}"], S[f"s{j+1}'"] = digit(n + j), 2 * digit(n + j)
    t = sum(digit(i) for i in range(n)) + 4 * sum(digit(n + j) for j in range(k))
    return S, t

S, t = reduce_3cnf_to_subset_sum(clauses, n)
print("S =", sorted(S.values(), reverse=True))
print("t =", t)

def subset_sum_witness(items, t):
    """枚举所有不超过 t 的可达和，reach[s] 记录凑出 s 的一个子集"""
    reach = {0: []}
    for name, x in items.items():
        for s, sub in list(reach.items()):
            if s + x <= t and s + x not in reach:
                reach[s + x] = sub + [name]
    return reach.get(t)

sol = subset_sum_witness(S, t)
print("凑出 t 的子集:", sol)
assign = {i: (f"v{i}" in sol) for i in range(1, n + 1)}
print("读出的赋值:", {f"x{i}": int(b) for i, b in assign.items()})
sat = lambda a: all(any(a[i] != neg for i, neg in C) for C in clauses)
print("该赋值满足公式:", sat(assign))
print("全部满足赋值:", [bits for bits in itertools.product([0, 1], repeat=n)
                     if sat({i + 1: bool(b) for i, b in enumerate(bits)})])

输出：

S = [1001001, 1000110, 101110, 100001, 11100, 10011, 2000, 1000, 200, 100, 20, 10, 2, 1]
t = 1114444
凑出 t 的子集: ['v1', "v2'", 'v3', "s1'", 's2', "s2'", "s3'", "s4'"]
读出的赋值: {'x1': 1, 'x2': 0, 'x3': 1}
该赋值满足公式: True
全部满足赋值: [(0, 0, 1), (0, 1, 0), (1, 0, 0), (1, 0, 1)]

构造出的 \(S\)、\(t\) 与原书完全一致。程序找到的子集对应赋值 \(x_1=1,x_2=0,x_3=1\)（原书举的是 \(x_1=0,x_2=0,x_3=1\)，二者都满足公式）。这段代码同时演示了"归约 + 解码"：若有一个快速的子集和算法，就能借它解 3-CNF-SAT。

34.6.4 代码二：基数约束的指数跟踪

从 \(N\) 只股票中选 \(K\) 只，在选定子集上优化权重（权重和为 1），使相对基准的跟踪误差最小。给定子集后，权重问题是带一个等式约束的二次规划，解一个 KKT 线性方程组即可；难点全在"选哪 \(K\) 只"。比较穷举（精确）与贪心前向选择（每次加入使跟踪误差下降最多的股票）。

import numpy as np, itertools, time
from math import comb

def make_instance(rng, N):
    B = rng.normal(1.0, 0.3, (N, 3)) * [1, 0.5, 0.3]          # 3 因子暴露
    F = np.diag([0.04, 0.02, 0.01])
    Sigma = B @ F @ B.T + np.diag(rng.uniform(0.01, 0.06, N))  # 因子模型协方差
    b = rng.dirichlet(np.full(N, 2.0))                           # 基准权重
    return Sigma, b

def te_given_subset(S, Sigma, b):
    """在子集 S 上、权重和为 1（不限符号）时的最小跟踪误差：解 KKT 线性方程组"""
    S = list(S); m = len(S); N = len(b)
    KKT = np.zeros((m + 1, m + 1))
    KKT[:m, :m] = 2 * Sigma[np.ix_(S, S)]; KKT[:m, m] = 1; KKT[m, :m] = 1
    rhs = np.append(2 * (Sigma @ b)[S], 1.0)
    w = np.zeros(N); w[S] = np.linalg.solve(KKT, rhs)[:m]
    d = w - b
    return np.sqrt(d @ Sigma @ d)

def brute_force(Sigma, b, K):
    return min(te_given_subset(S, Sigma, b) for S in itertools.combinations(range(len(b)), K))

def greedy(Sigma, b, K):
    S = []
    for _ in range(K):
        j = min((j for j in range(len(b)) if j not in S), key=lambda j: te_given_subset(S + [j], Sigma, b))
        S.append(j)
    return te_given_subset(S, Sigma, b)

rng = np.random.default_rng(5)
N, K = 20, 5
Sigma, b = make_instance(rng, N)
t0 = time.perf_counter(); te_bf = brute_force(Sigma, b, K); t_bf = time.perf_counter() - t0
print(f"N={N}, K={K}: 穷举 {comb(N, K)} 个子集用时 {t_bf:.2f}s，最优 TE {te_bf:.3%}；贪心 TE {greedy(Sigma, b, K):.3%}")

ratios = []
for _ in range(100):                                          # 100 个随机实例：贪心离最优多远
    Sigma, b = make_instance(rng, 14)
    ratios.append(greedy(Sigma, b, 4) / brute_force(Sigma, b, 4))
ratios = np.array(ratios)
print(f"100 个实例 (N=14, K=4)：贪心恰为最优 {np.mean(ratios < 1 + 1e-9):.0%}，平均比值 {ratios.mean():.4f}，最差 {ratios.max():.4f}")
for n_, k_ in [(50, 10), (300, 30), (800, 50)]:
    print(f"C({n_},{k_}) = {comb(n_, k_):.3e}")

输出：

N=20, K=5: 穷举 15504 个子集用时 0.15s，最优 TE 5.494%；贪心 TE 5.494%
100 个实例 (N=14, K=4)：贪心恰为最优 52%，平均比值 1.0253，最差 1.1967
C(50,10) = 1.027e+10
C(300,30) = 1.732e+41
C(800,50) = 9.823e+79

解读：

• 穷举 \(\binom{20}{5}=15504\) 个子集只要零点几秒，但 \(\binom{50}{10}\approx10^{10}\) 已经要几天，\(\binom{300}{30}\approx10^{41}\) 则永远算不完。这就是"指数级"在实践中的含义。
• 贪心在一半实例上找到了最优，平均只差 2.5%，最差差约 20%。它没有理论上的常数倍保证（跟踪误差目标不满足集合覆盖那种良好的结构），所以生产中常把贪心解作为 MIQP 分支定界的初始可行解，或用多次随机重启、交换型局部搜索改进。
• 这里为了简洁允许权重为负；加上多头约束 \(w\ge0\) 后，给定子集的子问题变成带不等式约束的 QP，结论不变。

34.6.5 代码三：伪多项式算法的代价

子集和的布尔 DP：reach[s] 表示能否凑出 \(s\)，每加入一个数 \(x\) 就把 reach 右移 \(x\) 位后取或。时间 \(O(nt)\)。

import numpy as np, time

def subset_sum_dp(xs, t):
    """布尔 DP：reach[s] 表示能否凑出 s。时间 O(n t)，对 t 的位数是指数级（伪多项式）"""
    reach = np.zeros(t + 1, dtype=bool); reach[0] = True
    for x in xs:
        if x <= t:
            reach[x:] |= reach[:t + 1 - x].copy()
    return reach

rng = np.random.default_rng(0)
n = 60
for digits in (5, 6, 7, 8):
    t = 10 ** digits
    xs = rng.integers(1, t // 10, n)
    t0 = time.perf_counter(); reach = subset_sum_dp(xs, t); dt = time.perf_counter() - t0
    best = np.flatnonzero(reach).max()
    print(f"t = 10^{digits}（t 有 {digits + 1} 位十进制）：用时 {dt:7.3f}s，不超过 t 的最大可达和 = {best}")

输出：

t = 10^5（t 有 6 位十进制）：用时   0.000s，不超过 t 的最大可达和 = 100000
t = 10^6（t 有 7 位十进制）：用时   0.002s，不超过 t 的最大可达和 = 1000000
t = 10^7（t 有 8 位十进制）：用时   0.027s，不超过 t 的最大可达和 = 10000000
t = 10^8（t 有 9 位十进制）：用时   0.282s，不超过 t 的最大可达和 = 100000000

\(t\) 每多一位数字，时间（和内存）乘以 10——对输入长度是指数级的，这正是 34.2.2 节说的伪多项式。实务含义：预算 1 亿元、以"元"为单位，DP 要 1 亿个状态，尚可；以"分"为单位就是 100 亿个状态，不可行。所以要么把金额粗粒度离散化（以"手"或"万元"为单位），要么用第 35 章的近似方案——它用"修剪"控制状态数，换来可证明的误差界。

本章小结

P 是多项式时间可求解的问题，NP 是解可多项式时间验证的问题，P ⊆ NP，二者是否相等是未解之谜。NP 完全问题是 NP 中最难的：任何一个有多项式算法，P 就等于 NP。比较难度的工具是多项式时间归约 \(L_1\le_PL_2\)，证明新问题难必须从已知难题归约过来。Cook–Levin 定理（电路可满足性 NP 完全）通过"把验证算法的计算展开成电路"建立了第一个 NP 完全问题，之后沿 SAT、3-CNF-SAT 归约出团、顶点覆盖、哈密顿回路、旅行商、子集和等。判定版本难则优化版本难；数值输入时要区分多项式与伪多项式。量化里的整手、基数约束、最小持仓、0-1 选择都让组合构建变成 NP 难的整数规划，应对办法是小规模精确求解、利用特殊结构和近似算法。

练习

基础

1. 说明为什么"判定问题 LONGEST-PATH（是否存在至少 \(k\) 条边的简单路径）∈ P"当且仅当"求最长简单路径长度的优化问题可多项式时间求解"。（原书 34.1-1。提示：对 \(k\) 二分或逐一询问。）
2. 0-1 背包的 \(O(nW)\) 动态规划是不是多项式时间算法？为什么？（原书 34.1-4。）
3. 证明：顶点数为奇数的二部图没有哈密顿回路。（原书 34.2-2。）
4. 证明 GRAPH-ISOMORPHISM ∈ NP，写出证书和验证算法。（原书 34.2-1。）
5. 证明 \(\le_P\) 是传递关系。（原书 34.3-2。）
6. 对 34.5.4 节的归约，画出公式 \(\phi=(x_1\vee\neg x_2\vee\neg x_3)\wedge(\neg x_1\vee x_2\vee x_3)\wedge(x_1\vee x_2\vee x_3)\) 对应的图，并找出一个 3-团。（原书图 34.14。答案之一：第一子句的 \(\neg x_2\)，第二、三子句的 \(x_3\)。）
7. 说明"按整手买入、每只至多一手、恰好花完预算"为什么是 NP 完全的。若改为"每只股票可以买任意多手"，问题还是 NP 完全吗？（提示：后者是无界子集和，仍为 NP 完全，但同样有伪多项式 DP。）

进阶

8. 假设有一个判定 SAT 的黑盒，说明如何在多项式次调用内构造一个满足赋值。（原书 34.4-6。）
9. 证明 2-CNF-SAT ∈ P：把子句 \((a\vee b)\) 看作蕴含 \(\neg a\to b\) 与 \(\neg b\to a\)，建有向图，用强连通分量判定。（原书 34.4-7。）
10. 证明 0-1 整数规划是 NP 完全的。（原书 34.5-2。提示：从 3-CNF-SAT 归约，每个子句写成一条"三个文字之和 ≥ 1"的线性约束，\(\neg x\) 写成 \(1-x\)。）
11. 证明集合划分问题（能否把整数集分成和相等的两半）是 NP 完全的。（原书 34.5-5。提示：从子集和归约，加入一两个精心选择的数。）
12. 在 34.6.4 节的代码中加入多头约束 \(w\ge0\)（用 scipy.optimize.minimize 或二次规划求解子问题），再比较贪心与穷举；然后实现"先解无基数约束的跟踪问题，保留权重最大的 \(K\) 只再重新优化"的截断启发式，比较三者。
13. 思考题 34-4：单机、\(n\) 个任务，加工时间、利润、截止期给定，按时完成才得利润。证明判定版本 NP 完全，并在加工时间都是 \(1..n\) 内的整数时给出动态规划算法。讨论它与"在收盘前分批执行一组订单"的关系。

原书推荐习题：34.1-4，34.2-1，34.2-2，34.3-2，34.4-6，34.4-7，34.5-2，34.5-3，34.5-4，34.5-5，思考题 34-1、34-4。

原书对照