NP-完全性

一、定义

存在大量重要的问题，它们在复杂性上大体是等价的。这些问题形成了一个类，叫做NP完全(NP-complete)问题。这些NP-完全性问题精确的复杂度仍然需要确定并且在计算机理论科学方面仍然是最重要的开放性问题。要么这些问题具有多项式时间揭发，要么它们都没有多项式时间解法。

二、难与易

在给定分类时，第一步要考虑的分界。许多问题可以用线性时间来求解。某些O(logN)的运行时间，但是它们要么假定已做某些预处理(如输入数据已读或数据结构已建立)，要么出现的在运算实例中。例如，gcd算法，当用于两个数M和N时，花费O(logN)时间。由于这两个数分别由logM和logN个二进制位组成，因此gcd算法实际上花费的时间对于输入数据的量或大小而言是线性的。由此可知，当我们度量运行时间时，我们将把运行时间考虑成输入数据的量的函数。一般来说，我们不能期望运行时间比线性更好。

另一方面，确实存在某些真正难的问题。这些问题时如此的难，以至于它们不可能解出。但这并不意味着只能发出感叹，期待天才来求解该问题。正如实数不足以表示x<x^2 的解那样，可以证明，计算机不可能解决碰巧发生的每一个问题。这些“不可能”解出的问题叫做不可判定问题(undecidable problem)。

一个特殊的不可判定问题是停机问题(halting problem)。是否能够让你的C编译器拥有一个附加的特性，即不仅能够检查语法错误，而且能够检查无限循环？这似乎是一个难的问题，但是我们或许期望，假如某些非常聪明的程序员花上足够的时间，他们也许能够编制出这种增强型的编译器。

该问题是不可判定问题的直观原因在于，这样一个程序可能很难检查它自己。由于这个原因，有时这些问题叫做递归不可判定的(recursively undecidable)。

如果一个无限循环检查程序能够写出，那么它肯定可以用于自检。此时我们可以制造一个程序叫做LOOP。LOOP吧一个程序P作为输入并使P自身运行。如果P自身运行时出现循环，则显示短语YES。如果P自身运行时终止了，那么自然要做的事是显示NO。替代这么做的办法是，我们将让LOOP进入一个无限循环。

根据我们的定义，如果P(P)终止，则LOOP(P)进入一个无限循环。设当P=LOOP时，P(P)终止。此时，按照LOOP程序，LOOP(P)应该进入一个无限循环。因此，我们必须让LOOP(LOOP)终止并进入一个无限循环，显然这是不可能的。另一方面，设当P=LOOP时P(P)进入一个无限循环，则LOOP必须终止，而我们得到同样的一组矛盾。因此，我们看到程序LOOP不可能存在。

三、NP类

NP类在难度上逊于不可判定问题的类。NP代表非确定型多项式时间(nondeterministic polynomial-time)。确定型机器在每一时刻都在执行一条指令，这是惟一确定的。而一台非确定型机器对其后的步骤是有选择的。它可以自由进行它想要的任意的选择，如果这些后面的步骤中有一条导致问题的解，那么它将总是选择这个正确的步骤。因此，非确定型机器具有非常好的猜测(优化)能力。这就好像一个奇怪的模型，因为没有人能够构建一台非确定型计算机，还因为这台机器是对标准计算机的令人难以置信的改进(此时每一个问题都变成易解的了)。我么将看到，非确定性是非常有用的理论结构。此外，非确定性也不像人们想象的那么强大。例如，即使使用非确定性，不可判定问题仍然还是不可判定的

检验一个问题是否属于NP的简单方法是用“是/否(yes/no)问题”的语言描述该问题。如果我们能在多项式时间内能够证明一个问题的任意“是”的实例时正确的，那么该问题属于 NP类。我们不必担心“否”的实例，因为程序总是进行正确的选择。因此对于汉密尔顿圈问题，一个“是”的实例就是圈中任意的一个包含所有顶点的简单的回路。由于给定一条路径，验证它是否真的是汉密尔顿圈是一件简单的事情，因此汉密尔顿圈问题属于NP。诸如“存在长度大于K的简单路径吗？”这样的适当问题也可能容易验证从而属于NP，满足这条件性质的任何路径可容易地检验。

由于解本身显然提供了验证方法，因此，NP类包括所有具有多项式时间解的问题。人们会想到，既然验证一个答案要比经过计算提出一个答案容易得多，因此在NP中就会存在不具有多项式时间解决的问题。这样的问题至今没有发现，于是，非确定性不是如此中重要的改进是完全有可能的，尽管有些专家很可能不这么认为。问题在于，证明指数下界是一项极其困难的工作。我们曾用来证明排序需要\Omega(N \log N) 次比较的信息理论定界方法似乎还不足以完成这样的工作，因为决策树都还不足够大。

还要注意，不是所有的可判定问题都属于NP，考虑确定一个图是否没有汉密尔顿的问题。证明一个图有汉密尔顿圈是相对简单的一件事情------我们只需展示一个即可。然而却没有人知道如何以多项式时间证明一个图没有汉密尔顿圈。似乎人们只能枚举所有圈并且将它们一个一个验证才行。因此，无汉密尔顿圈的问题不知属不属于NP。

四、NP-完全问题

在已知属于NP的所有问题中，存在一个子集，叫做NP-完全(NP-complete)问题，它包含了NP中最难的问题。NP-完全问题有一个性质，即NP中任一问题都能够多项式地归约成NP完全问题。

一个问题P1可以归约成问题P2如下：设有一个映射，使得P1的任何实例都可以变换成P2的一个示例。求解P2，然后将答案映射回原始的解答。作为一个例子，考虑吧数以十进制输入到一个计算器。将这些十进制数转化成二进制数，所有的计算都用二进制进行。然后，再把最后答案转变成十进制显示。对于可多项式归约成P2的P1，与变换和联系的所有工作必然以多项式时间完成。

NP-完全问题时最难的NP问题的原因在于，一个NP-完全的问题基本上可以用作NP中任何问题的子程序，其花费只不过是多项式的并行开销量。因此，如果任意NP完全问题有一个多项式时间的解。这使得NP完全问题时所有NP问题中最难的问题。

设我们有一个NP-完全性问题P1，并设P2已知属于NP。再进一步假设P1多项式地归约成P2，使得我们可以通过使用P2来求解P1而只多损耗了多项式时间。由于P1是NP完全的，NP中的每一个问题都可以多项式地归约成P1。应用多项式的封闭性，我们看到，NP中的每一个问题均可多项式地归约成P2：我们把问题归约成P1，再把P1归约成P2。因此，P2是NP完全的。