NP-hard 问题

什么是 NP-hard 问题

我们先从两个相似的问题开始讨论：最小生成树（minimum spanning tree, MST）问题和旅行商问题（traveling salesman problem, TSP），它们都是图论中的经典问题。

最小生成树问题的形式化描述如下：给定一个连通的无向图 $G=(V, E)$，其中 $V$ 是顶点集合，$E$ 是边集合，每条边都有一个非负权重 $w_e$。目标是找到一个生成树 $T$，$T$ 包含图 $G$ 的所有顶点，并且 $T\subseteq E$，使得 $T$ 的总权重最小，即 $\sum_{e \in T} w_e$ 最小。

一个图可能有指数级多个生成树，除了很小的图之外，穷举法往往不可行。但是 MST 问题有很多巧妙快速的算法，比如 Prim 算法和 Kruskal 算法，它们都能在多项式时间内解决 MST 问题，准确地说，运行时间复杂度是 $O((|V|+|E|)\log|V|)$。

旅行商问题的形式化描述如下：给定一个完全图 $G=(V, E)$，每条边都有一个非负权重 $w_e$，目标是找到一个巡回路线（tour）$T$，该路线经过每个顶点恰好一次，并且返回到起点，使得巡回路线的总权重最小，即 $\sum_{e \in T} w_e$ 最小。

不妨令 $n=|V|$，那么 TSP 问题的解空间大小为 $(n-1)!/2$，这是一个指数级的大小。我们可以任选一点作为起点，有 $n$ 种选法，下一步可以是剩余的任意一点，有 $n-1$ 种选法，以此类推，最后一步必须回到起点，所以总共有 $n!$ 种选法。由于每条巡回路线可以沿两个方向遍历，起点也可以任选，因此每条路线都被重复计算了 $2n$ 次，所以共有 $n!/(2n)=(n-1)!/2$ 条不同的巡回路线。

这个问题乍一看和最小生成树问题相当类似，形式化表达几乎一样，都是在一个图中寻找一个边的子集，使得这个子集包含所有顶点，并且总权重最小。但是截至目前，还没有人找到解决 TSP 问题的多项式时间算法。通俗地说，多项式时间算法就是一种相对快速的算法，比如很多算法都是线性时间或近似线性的，我们希望最坏情况下的运行时间随输入规模增长而缓慢增长。

对于这个问题有两种可能：（1）存在解决 TSP 问题的多项式时间算法，但是我们还没有发现它；（2）不存在解决 TSP 问题的多项式时间算法。

TSP 问题就是 NP-hard 问题的一个例子。NP-hard 理论的意义在于用一种精确的方式，把问题划分为“计算上容易”（如 MST 问题）和“计算上困难”（如 TSP 问题）两类。下面会由浅入深地一步步讨论 NP-hard 问题的定义和相关理论。

• 知道什么是 NP-hard 问题
• 对 NP-hard 问题有基本的理解
• 掌握如何近似求解 NP-hard 问题
• 知道若干 NP-hard 问题的例子，掌握证明一个问题是 NP-hard 问题的基本方法
• 对 NP-hard 问题的数学理论有初步的理解

NP-hard 理论将容易和困难的问题区分开来。一个相当简化的说法是，容易的问题可以在多项式时间内解决，而困难的问题在最坏情况下需要指数时间才能解决。

下面给出几个容易的问题及其求解算法和时间复杂度：

问题	算法	时间复杂度
最小生成树	Prim 算法	$O((\lvert V \rvert+\lvert E \rvert)\log\lvert V \rvert)$
最短路径	Dijkstra 算法	$O((\lvert V \rvert+\lvert E \rvert)\log\lvert V \rvert)$
排序	快速排序（平均）	$O(n\log n)$
强连通分量	Kosaraju 算法	$O(\lvert V \rvert+\lvert E \rvert)$
序列比对	动态规划	$O(nm)$

这些算法的时间复杂度各不相同，但它们的复杂度上界都是多项式时间的，即运行时间的上界由输入规模和某个多项式函数共同确定。

多项式时间算法（polynomial time algorithm）是指最坏情况运行时间为 $O(n^d)$ 的算法，其中 $n$ 是输入规模，$d$ 是一个常数，与 $n$ 的大小无关。大部分教科书上常见的算法是多项式时间算法，而且指数 $d$ 都比较小。不过并不是所有算法都能在多项式时间内完成，比如穷举所有可能的解，运行时间随输入规模呈指数增长。任何指数函数最终都会比任何多项式函数增长得快得多，两者之间存在巨大的差异。

摩尔定律指出，在给定的成本预算下，计算能力每 1-2 年翻一番。但这并不意味着多项式算法和指数算法之间的差距会缩小甚至消失。相反，需要计算的规模会随着计算能力一同增长，多项式算法和指数算法之间的差距反而会越来越大。比如计算能力翻一番，线性时间复杂度的算法在相同时间内能处理的输入规模也翻一番，平方时间复杂度的算法在相同时间内能处理的输入规模变为原来的 $\sqrt{2}$ 倍，而指数时间复杂度的算法在相同时间内只能让输入规模增加 1。随着计算能力的增长，指数时间复杂度的算法能够处理的输入规模几乎没有增长，而多项式时间复杂度的算法能够处理的输入规模增长很快。

NP-hard 理论将容易的问题定义为多项式时间可解的（polynomial time solvable）问题。严格来说，一个 $O(n^{100})$ 的算法也是多项式时间算法，但是它的运行时间在实际中是不可接受的。反过来想，如果 TSP 问题不是多项式时间可解的问题，那么连一个 $O(n^{100})$ 甚至 $O(n^{10000})$ 的求解算法都不存在。

假定我们怀疑 TSP 问题是不容易的问题，即无法被任何多项式时间算法求解。如何确定这一点呢？最有说服力的办法是严格的数学证明。但很不幸的是，至今没人能找到多项式时间算法来解决 TSP 问题，也没有人能证明这样的算法不存在。那么如何判断一个问题是困难问题呢？NP-hard 理论采用了相对难度的概念：只要一个问题至少和众多尚未解决的问题一样难，就可以宣布它也是困难问题。

TSP 是困难问题吗？如何证明呢？一个比较弱的证据是，成百上千的研究者几十年来都未能攻克这个问题，没能找到一个多项式时间算法。这个问题和大量未解问题一样难，也可以说与“给定一个解就能在多项式时间内验证其正确性”的问题一样难。一个更强的证据是，如果 TSP 有多项式时间算法，那么就能解决成千上万个问题，而这些问题让更多的研究者数十年来都未能攻克。NP-hard 理论表明这成千上万个问题（包括 TSP）不过是同一个问题的变体。

NP-hard 理论的核心是：一个问题属于 NP-hard，当且仅当它至少与每一个“解能够在多项式时间内验证其正确性”的问题一样难。

和 NP-hard 相关的一个概念是 $\text{P}\neq\text{NP}$ 猜想。这里的 $\text{P}$ 指可以在多项式时间内求解的问题，$\text{NP}$ 指可以在多项式时间内验证解的正确性的问题。$\text{P}\neq\text{NP}$ 猜想认为，存在一些问题虽然可以在多项式时间内验证解的正确性，但无法在多项式时间内求解。换句话说，检查一个问题的候选解是否正确比找到这个解要容易得多。

利用这个猜想，可以给 NP-hard 问题下一个非正式的定义：如果一个问题是 NP-hard 问题，那么针对它的多项式时间算法会推翻 $\text{P}\neq\text{NP}$ 猜想。任何针对 NP-hard 问题的多项式时间算法都意味着该猜想为假，从而每一个“解可以在多项式时间内验证”的问题都能找到多项式时间的求解算法。在 $\text{P}\neq\text{NP}$ 猜想成立的前提下，NP-hard 问题都无法在多项式时间内求解，甚至不存在 $O(n^{100})$ 或 $O(n^{10000})$ 这样的多项式时间算法。

随机化算法能够逃出 NP-hard 理论的束缚吗？大肆宣传的量子算法呢？答案是否定的。事实上，随机化算法可以看作是量子算法的一个特例。大规模通用量子计算机如果能够实现，也只会在极少数问题上改变游戏规则，比如极其重要的大整数分解问题。不过这个问题不被认为是 NP-hard 问题。专家的猜测是，即使是量子计算机，也无法在多项式时间内求解 NP-hard 问题。因此，NP-hard 问题带来的挑战依然存在。

最后，我们在绝大部分场景中遇到的问题，要么是容易的问题，多项式时间可解，要么是 NP-hard 问题。不过也有极少数例子介于两者之间，比如整数分解问题和图同构问题，这两个问题都有次指数时间（但不是多项式时间）的算法：指数时间算法比次指数时间算法慢得多，而次指数时间算法又比多项式时间算法慢得多。

应对策略

当我们在工作中遇到 NP-hard 问题时，我们要明确我们的预期。我们不应该期待一个针对 NP-hard 问题的通用且高效的多项式时间算法。除非问题足够小或者输入具有良好的结构，否则我们需要付出很大的精力才能解决问题，同时可能还需做出一些妥协。

NP-hard 理论使得我们无法找到同时满足下面三个性质的算法，这是一个不可能三角。

• 通用（general purpose）：算法能够处理所有可能的输入实例。
• 正确（correct）：算法对每一个输入实例都能给出正确的解。
• 快速（fast）：算法在多项式时间内运行。

所以我们不得不放弃其中一个性质。

第一种策略是放弃通用性，转而关注与应用相关的特殊情况。最好的情况是你能识别出特定领域的约束，并设计出一个在有约束的输入上总是正确且快速的算法。动态规划中就有这样的例子。

第一个例子是带权独立集问题。这个问题的输入是无向图 $G=(V,E)$，以及每个顶点 $v\in V$ 的非负权重 $w_v$。目标是找到一个顶点子集 $S\subseteq V$，使得 $S$ 中没有相邻的顶点，并且 $\sum_{v\in S}w_v$ 最大。这里的 $S$ 就是独立集（independent set）。例如，如果边表示冲突（比如课程之间的冲突），那么独立集就对应着没有冲突的集合。在一般情况下，带权独立集问题是 NP-hard 的。不过在之前动态规划中分析过的一个特例里，$G$ 是路径（path），顶点是 $v_1,v_2,\dots,v_n$，边是 $(v_i,v_{i+1})$，此时可以通过动态规划在线性时间内求解。这个算法可以推广到无环图。

第二个例子是背包问题。这个问题的输入是 $n$ 个物品的价值 $v_1,v_2,\dots,v_n$ 和大小 $s_1,s_2,\dots,s_n$，以及背包的容量 $C$。目标是选择一个物品子集 $S\subseteq \{1,2,\dots,n\}$，使得 $\sum_{i\in S}s_i\le C$，并且 $\sum_{i\in S}v_i$ 最大。这个问题的目标是以最有价值的方式利用资源。比如预算有限时，如何在能力和期望薪资各不相同的求职者中做选择；或者把钱花在哪些商品和服务上才能获得最大价值。这个问题是 NP-hard 的。该问题有一个 $O(nC)$ 的动态规划算法，但只有当 $C$ 被 $n$ 的多项式函数界定时，它才是多项式时间算法。

第二种策略在时间敏感的应用中尤其流行：坚持通用性和速度，牺牲正确性。不总是正确的算法有时被称为近似算法（approximation algorithm）或启发式算法（heuristic algorithm）。

理想情况下，算法大致是正确的，这意味着它满足以下一条或者两条性质：

• 算法在大多数输入上是正确的。
• 算法在每一个输入上都几乎是正确的。

第二个性质对于最优化问题很常见。优化问题的目标是找到一个可行解，使得目标函数的值最优。几乎正确意味着算法输出的解在目标函数值上接近最优解，而不一定严格最优。比如旅行商问题，算法输出的是一条总成本不会比最优巡回路线高出太多的巡回路线。

最后一种策略适用于那些不能牺牲正确性、因而不能采用启发式算法的应用。对于 NP-hard 问题，每一个正确的算法都必定在某些输入上至少要以超多项式时间运行，因此目标就变成了设计一个尽可能快的算法，它要比朴素的穷举法有显著改进。这意味着算法需要满足下面一条或者两条性质：

• 算法在应用相关的输入上通常运行得很快。
• 算法在每一个输入上都比穷举法更快。

在第二种情况下，算法在某些输入上还是以指数时间运行，但是比朴素的穷举法要快得多。比如后面会分析如何用动态规划求解 TSP 问题，运行时间从 $O(n!)$ 降到 $O(n^2\cdot 2^n)$，这在实际应用中已经是一个显著的改进，但是依旧是指数时间的。

因此，我们要理解 NP-hard 问题是无处不在的，实际应用中到处都是这类问题，而且它们通常在计算上非常困难，没有总能在多项式时间内求解的算法。但是这不意味着这些问题不能在实践中解决，我们可以在通用性、正确性或者速度上做出妥协，从而在实际应用中找到可行的解决方案。

归约法证明 NP-hard 问题

在日常工作中，我们需要识别哪些问题是 NP-hard 的，从而调整我们的算法设计策略，不在这种问题上白白浪费时间。

首先，需要掌握一批简单而常见的 NP-hard 问题。后面会介绍常见的 19 个问题。最简单的情况是我们遇到的问题可以直接归结为其中之一。其次，需要发现问题之间的归约关系，将一个已知的 NP-hard 问题归约到我们关心的问题上，从而证明它也是 NP-hard 的。也就是说，任何至少与某个 NP-hard 问题 $A$ 一样困难的问题 $B$，本身也是 NP-hard 的。

如果求解问题 $B$ 的算法可以被轻易地翻译成求解问题 $A$ 的算法，我们就说问题 $A$ 归约（reduce）到问题 $B$。换句话说，问题 $A$ 可以通过多项式次数调用问题 $B$ 的子程序，再加上多项式数量的额外工作来求解。

比如把找整数数组中位数的问题归约到对该数组排序的问题。对数组排序后，返回中间的元素即可得到中位数。找中位数的问题是 $A$，可以通过调用排序（问题 $B$）的算法，得到排序后的数组，再返回中间的元素，从而求解问题 $A$。因此可以说问题 $A$ 归约到了问题 $B$。这里排序可以使用快速排序、归并排序等算法，时间复杂度是 $O(n\log n)$，那么找中位数问题可以在 $O(n\log n)$ 时间内求解，因为额外工作量是 $O(1)$。

假设问题 $A$ 可以通过至多 $T_1(n)$ 次调用问题 $B$ 的子程序，并执行至多 $T_2(n)$ 的额外工作来求解。如果 $B$ 算法的运行时间为 $T_3(n)$，直觉理解是总运行时间大约为 $T_1(n)\cdot T_3(n)+T_2(n)$。不过这里的额外工作可能会使传给子程序的输入规模从 $n$ 变得更大（与 $T_2(n)$ 相关），这会影响每次调用 $B$ 时的运行时间。因此 $A$ 的时间复杂度是 $T_1(n)\cdot T_3(T_2(n)) + T_2(n)$。

如果 $T_1(n),T_2(n)$ 和 $T_3(n)$ 都是多项式函数，那么 $A$ 的时间复杂度也是多项式的。这说明如果我们能在多项式时间内求解问题 $B$，并且问题 $A$ 可以归约到问题 $B$，那么问题 $A$ 也能在多项式时间内求解。

如果问题 $A$ 可以归约到 $B$，并且 $A$ 是 NP-hard 的，那么 $B$ 也必须是 NP-hard 的。换句话说，如果我们能在多项式时间内求解 $B$，那么也能在多项式时间内求解 $A$，这与 $A$ 的 NP-hard 性质相矛盾。因此，$B$ 也必须是 NP-hard 的。

因此我们只需要下面两步就可以证明一个问题是 NP-hard 的：

1. 选择一个已知的 NP-hard 问题 $A$。
2. 证明问题 $A$ 可以归约到我们关心的问题 $B$。

下面看一个具体的例子：证明无环最短路径问题是 NP-hard 的。

单源最短路径问题（single-source shortest path problem）是指给定一个有向图 $G=(V,E)$、每条边 $e\in E$ 的实数长度 $\ell_e$，以及一个起点 $s\in V$，求从 $s$ 到每个顶点 $v\in V$ 的最短路径长度 $\mathrm{dist}(s,v)$。如果不存在这样的路径，那么 $\mathrm{dist}(s,v)=+\infty$。一个重要的点是这里允许有环且边长可以为负。

如果边长不能为负数，那么这个问题可以在多项式时间内求解，例如使用 Dijkstra 算法。

如果图中出现了负环（negative cycle），即一个有向环的边长之和为负，那么单源最短路径问题就没有最优解，因为可以沿着负环无限次循环，使路径长度不断减小。为了避免这种情况，我们可以考虑无环最短路径问题，即要求路径中不允许出现环，也就是说每个顶点至多被访问一次。输入的图可以有负环，但路径中不能经过这些负环。如果输入的图中没有负环，最短路径也就是无环的，可以使用 Bellman-Ford 算法求解。

因此我们将问题明确为无环最短路径（cycle-free shortest path）问题。输入是一个有向图 $G=(V,E)$、一个起点 $s\in V$，以及每条边 $e\in E$ 的实数长度 $\ell_e$。输出是对每个顶点 $v\in V$，求一条无环的 $s-v$ 路径的最小长度（如果不存在这样的路径，则为 $+\infty$）。

很不幸，这个问题是 NP-hard 的。下面我们就来证明这一点。

第一步找到一个已知的 NP-hard 问题 $A$。这里使用有向哈密顿路径（directed Hamiltonian path）问题。该问题的输入是一个有向图 $G=(V,E)$，起点 $s$ 和终点 $t$，输出是判断图中是否存在一条从 $s$ 出发、到 $t$ 结束、且恰好经过每个顶点一次的路径。后面我们会证明这个问题是 NP-hard 的，这里先把它当作已知的 NP-hard 问题。

第二步证明问题 $A$ 可以归约到无环最短路径问题 $B$。无环最短路径问题的输入是一个有向图 $G=(V,E)$、起点 $s$，有向哈密顿路径问题的输入恰好提供了这些信息。不过无环最短路径问题要求每条边有一个权重，即每条边都有一个实数长度 $\ell_e$。为了进行归约，我们可以将有向哈密顿路径问题的每条边赋予长度 $-1$，那么最短路径就是跳数最多的路径。如果从 $s$ 到 $t$ 的最短无环路径长度为 $-(|V|-1)$，因为无环路径不能有重复顶点，经过所有顶点需要 $|V|-1$ 跳，那么此时存在一条经过每个顶点一次的路径，即有向哈密顿路径存在。反之，如果 $s$ 到 $t$ 的最短无环路径长度大于 $-(|V|-1)$，那么说明跳数少于 $|V|-1$，也就是说有的顶点不包含在路径中，所以不存在经过每个顶点一次的路径，即有向哈密顿路径不存在。因此，有向哈密顿路径问题可以归约到无环最短路径问题，从而证明无环最短路径问题是 NP-hard 的。