3.1.1. 困难问题¶

一个问题可能被认为是难（hard）的，途径有多种。 例如，我们可能难以理解问题本身的定义。 在一个大型数据收集与分析项目开始时，开发人员及其客户可能对自身目标只有一个模糊的概念，需要随着时间的推移逐步理清。 对于其他类型的问题，我们可能难以找到或理解用来求解该问题的算法。 理解口语英语并将其翻译成书面文字就是一个例子：这类问题的目标易于定义，但其解却不容易发现。 不过，尽管自然语言处理算法的编写可能很困难，程序的运行时间却可能相当快。 当今有许多实用系统能在合理的时间内解决该问题的某些方面。

以上这些都不是计算机理论家使用"hard"一词时的通常含义。 在本节中，"hard" 是指该问题的已知最佳算法在运行时间上代价高昂。 困难问题的一个例子是 汉诺塔问题。 理解该问题及其解法很容易，编写求解该问题的程序也很容易。 但对任何"合理的"较大 \(n\) 值来说，运行它都需要极长的时间。 试着运行一个只求解 30 个圆盘的汉诺塔问题的程序吧！

汉诺塔问题需要指数级时间，也就是说，其运行时间为 \(\Theta(2^n)\)。 这与需要 \(\Theta(n \log n)\) 时间或 \(\Theta(n^2)\) 时间的算法有本质区别， 甚至与需要 \(\Theta(n^4)\) 时间的问题也有本质区别。 这些都是多项式运行时间的例子，因为这些方程所有项的指数都是常数。 如果我们购买一台运行速度提高一倍的新计算机，那么在给定时间内我们能解决的复杂度为 \(\Theta(n^4)\) 的问题规模，将增加 2 的四次方根倍。 换句话说，问题规模会有一个乘法因子上的提升，即使这个因子相当小。 对于任何运行时间可以用多项式表示的算法，都是如此。

试想：如果你购买一台速度加倍的计算机，并试图在给定时间内求解更大的汉诺塔问题，会发生什么。 由于其复杂度为 \(\Theta(2^n)\)，我们只能求解多一个圆盘的问题！ 这里没有任何乘法因子，并且这对任何指数级算法都成立： 处理能力按常数因子提升，只会带来求解能力上固定的增量。

多项式运行时间与指数级运行时间之间还有其他许多根本性的差异，这些差异支持将二者视为本质不同的类型。 多项式在复合与加法运算下是封闭的。 因此，顺序运行多项式时间程序，或者让一个多项式运行时间的程序以多项式次数调用另一个程序，结果仍然是多项式时间。 此外，所有已知的计算机都是多项式相关的。 也就是说，任何程序只要今天能在任意一台计算机上以多项式时间运行，那么转移到任何其他计算机上仍然会以多项式时间运行。

在实际应用中，认识到区分的理由是实用的。实际上，大多数多项式时间算法是“可行的”，因为它们可以在合理的时间内处理相当大的输入。相比之下，大多数需要指数时间算法在处理相当适度的输入时也是不实用的。有人可能会认为，一个多项式度（如 \(n^{100}\) ）高的程序是不实用的，而一个指数时间算法的成本为 \(1.001^n\) 的算法是实用的。但现实情况是，我们几乎没有遇到最好的多项式时间算法的度（几乎所有算法的度都为四或以下），而几乎没有指数时间算法（其成本为 \((O(c^n))\) ）的常数（为 \(c\) ）接近于一。因此，在实际应用中，多项式时间算法和指数时间算法之间的灰色地带并不多。

在本模块中，我们把 困难算法 定义为以指数级时间运行的算法， 也就是对某个常数 \(c > 1\) 运行时间为 \(\Omega(c^n)\) 的算法。 关于困难 问题 的定义将很快给出。

3.1.2. NP 完全性理论¶

设想一台魔法计算机，它通过在问题的所有可能解中猜出正确答案来工作。 如果你不喜欢魔法，那么可以想象一台超并行计算机，它能同时测试所有可能解（无论有多少个）。 显然，这台魔法（或高度并行）计算机能做普通计算机能做的一切， 它还可能比普通计算机更快地解决某些问题（这里的"更快"意味着不只是按常数甚至多项式因子加速）。 考虑某个问题：给定一个解猜测后，检验该解是否正确可以在多项式时间内完成。 即使可能解的数量是指数级的，任何一个给定猜测都可以在多项式时间内被检验 （等价地，所有可能解都在多项式时间内被同时检验）， 因此我们假想的魔法（或高度并行）计算机可以在多项式时间内解决该问题。 对这一概念的另一种看法是：如果你无法通过先猜测正确答案再检验它而在多项式时间内得到问题的答案，那么你也无法以任何其他方式在多项式时间内做到。

对问题正确答案的"猜测"—或并行检验所有可能解以确定哪一个是正确的—这一概念被称为 非确定性选择。 以此方式工作的算法被称为 非确定性算法， 任何具有在非确定性机器上以多项式时间运行的算法的问题，都有一个特殊的名称： 我们说它属于 NP 问题。 因此，NP 中的问题就是那些能在非确定性机器上以多项式时间解决的问题。

并非所有在普通计算机上需要指数级时间的问题都属于 NP。 例如，汉诺塔问题就 不 在 NP 中，因为它必须为 \(n\) 个圆盘打印出 \(O(2^n)\) 次移动。 非确定性机器无法在更短的时间内"猜出"并打印出正确答案。

另一方面，考虑 TRAVELING SALESMAN （推销员）问题。

这个版本有时被称为 优化问题， 因为我们试图找到最小（或最优）的解。

图 28.3.1 说明了这个问题。 图中显示了五个顶点，每一对顶点之间都有边及相应的代价。 （为简单起见，图 28.3.1 显示的是无向图，假定两个方向的代价相同，尽管实际情况不一定是这样。） 如果推销员按 ABCDEA 的顺序访问各个城市，总行程为 13。 更优的路线是 ABDCEA，代价为 11。 对这张特定的图来说，最佳路线是 ABEDCA，代价为 9。

我们无法用"先猜后验"的非确定性计算机在多项式时间内解决该问题。 问题在于：给定一个候选回路，虽然我们可以快速检验该答案确实是一条形式正确的回路， 也可以快速计算出回路的长度，但我们没有简便的方法知道它是否确实是 最短 的回路。 不过，我们可以解决该问题的一个变体，即 判定问题 形式。 判定问题就是答案要么是 YES 要么是 NO 的问题。 TRAVELING SALESMAN 的判定问题形式如下。

我们可以用非确定性计算机在多项式时间内解决这个版本的问题。 非确定性算法只是并行地检查图中所有可能的边子集。 如果任何一个边子集构成一条总长度小于或等于 \(k\) 且包含所有顶点的适当回路，答案为 YES；否则答案为 NO。 注意，只需要 某个 子集满足要求即可，有多少个子集失败并不重要。 检验某个特定子集在多项式时间内即可完成：把各条边的距离相加，并验证这些边构成一条恰好访问每个顶点一次的回路。 因此，检验算法在多项式时间内运行。 遗憾的是，需要检验的子集有 \(2^{|{\mathrm E}|}\) 个， 所以该算法无法转换为在普通计算机上运行的多项式时间算法。 世界上也没有任何人知道在普通计算机上求解 TRAVELING SALESMAN 的任何其他多项式时间算法， 尽管数十年来许多计算机科学家已对该问题进行了广泛研究。

事实证明，具有这种性质的问题有一大类: 我们知道高效的非确定性算法，但不知道是否存在高效的确定性算法。 与此同时，我们也无法证明其中任何一个问题 不 存在高效的确定性算法。 这一类问题被称为 NP 完全问题。 NP 完全问题真正奇特而迷人的地方在于：如果有人找到了其中任何一个问题的、能在普通计算机上多项式时间运行的解法， 那么通过一系列归约，NP 中的每一个其他问题也都能在普通计算机上多项式时间求解！

如果 NP 中的 任意 问题都能在多项式时间内归约为问题 \(X\)，则称问题 \(X\) 为 NP 困难。 因此，\(X\) 与 NP 中的任何问题 一样难 。 若问题 \(X\) 满足以下条件，则定义为 NP 完全（NP-complete）：

1. \(X\) 在 NP 中，且

2. \(X\) 是 NP 困难的。

要求一个问题为 NP 困难或许看起来不可能，但事实上这样的问题有数百个，包括 TRAVELING SALESMAN 。 另一个这样的问题叫做 K-CLIQUE 。

Settings

Saving...
Server Error
Resubmit

目前没有人知道 K-CLIQUE 是否存在多项式时间解法， 但如果为 K-CLIQUE 或 为 TRAVELING SALESMAN 找到了这样的算法， 那么该解法就可以被修改，用来在多项式时间内求解另一个问题或 NP 中的任何其他问题。

知道问题 P1 是 NP 完全的主要理论优势在于，它可以用来证明另一个问题 P2 是 NP 完全的。 做法是找到从 P1 到 P2 的多项式时间归约。 因为我们已知 NP 中的全部问题都能在多项式时间内归约为 P1（依据 NP 完全的定义）， 现在我们就知道所有问题也都能归约为 P2，方法很简单：先归约到 P1，再从那里归约到 P2。

知道一个问题是 NP 完全还有一个实际的优点。 它意味着：如果能为 任意 一个 NP 完全问题找到多项式时间解，那么就能为 所有 这样的问题找到多项式时间解。 其含义是：

1. 因为还没有人找到这样的解，所以这样做必然很困难或不可能；而且

2. 为某一个 NP 完全问题寻找多项式时间解所付出的努力，可以看作是为所有 NP 完全问题所付出的。

NP 完全性对普通程序员有什么实际意义呢？ 好吧，如果你的老板要求你提供一个快速算法来解决问题， 而你回来说你最多只能做到指数级时间算法，他们是不会高兴的。 但是，如果你能证明该问题是 NP 完全的，虽然他们仍然不会高兴，至少他们不应该生你的气！ 通过证明他们的问题是 NP 完全的，你实际上是在说： 50 多年来，最杰出的计算机科学家一直在试图为这个问题寻找多项式时间算法，却都失败了。

在普通计算机上能在多项式时间内解决的问题，被称为属于类 P（class P）。 显然，P 中所有问题都能在非确定性计算机上多项式时间求解，只需不使用非确定性能力即可。 NP 中的一些问题属于 NP 完全。 我们可以把所有能用指数级时间或更好时间解决的问题看作一个更大的问题类， 因为所有能在多项式时间内解决的问题，也都能在指数级时间内解决。 因此，我们可以按照图 28.3.2 来审视指数级时间或更好时间问题的世界。

理论计算机科学中最重要而未解答的问题是 \(P = NP\) 是否成立。 如果二者相等，那么 TRAVELING SALESMAN 及其所有相关问题都存在多项式时间算法。 因为已知 TRAVELING SALESMAN 是 NP 完全的，如果为该问题找到了多项式时间算法， 那么 NP 中的 所有 问题也都将能在多项式时间内求解。 反过来，如果我们能证明 TRAVELING SALESMAN 存在指数级时间下界， 那么我们就知道 \(P \neq NP\)，并且没有任何 NP 完全问题能在多项式时间内求解。