《算法导论》第三十四章（续1）

34.1多项式时间

在开始研究NP完全性之前，先来形式化地定义一下多项式时间可解问题。我们通常都把这些问题看做是易处理的，其原因是哲学方面的，而不是数学的。我们可以提供三点论据:

第一，虽然把所需运行时间为&(n0)的问题作为“难处理问题”也有其合理之处，但在实际中却只有极少数问题需要如此高次的多项式时间。在实际中，所遇到的典型多项式时间可解问题所需的时间要少得多。经验表明，一旦某一问题的第一个多项式时间算法被发现后，往往跟着就会发现更为有效的算法。即使对某个问题来说，当前最佳算法的运行时间为&(n0)，也很有可能在极短的时间内又会发现运行时间更短的算法。

第二，对很多合理的计算模型来说，在一个模型上用多项式时间可解的问题，在另一个模型上也可以在多项式时间内解决。例如，用本书中大量使用的串行随机存取计算机在多项式时间内可求解的问题类，与抽象的图灵机上在多项式时间内可求解的问题类是相同的9，而且，即使处理器数目随输入规模以多项式增加，它也与利用并行计算机在多项式时间内可求解的问题类相同。

第三，由于在加法、乘法和组合运算下多项式是封闭的，因此，多项式时间可解问题具有很好的封闭性。例如，如果一个多项式时间算法的输出传送给另一个多项式时间算法作为输人，则得到的组合算法仍是多项式时间算法。练习34.1-5要求读者证明:如果一个多项式时间算法对另一个多项式时间的子程序进行常数次调用，那么组合算法的运行时间也是多项式的。

抽象问题

为了理解多项式时间可解问题类，首先必须对所谓的“问题”这一概念进行形式化定义。定义抽象问题Q为在问题实例集合Ⅰ和问题解集合S上的一个二元关系。例如，SHORTEST-PATH的一个实例是由一个图和两个顶点所组成的三元组。其解为图中的顶点序列，序列可能为空(两个顶点间不存在通路)。SHORTEST-PATH问题本身就是一个关系，它把图的每个实例和两个顶点与图中联系这两个顶点的最短路径联系在了一起，因为最短路径不一定是唯一的，因此，一个给定的问题实例可能有多个解。

抽象问题的这个形式定义对我们的要求来说显得太笼统。为了简单起见，NP完全性理论把注意力集中在判定问题上，即那些解为“是”或“否”的问题。于是，我们可以把抽象的判定问题看做是从实例集Ⅰ映射到解集{0，1}上的一个函数。例如，一个与SHORTEST-PATH有关的判定问题是我们先前见到过的较为简单的PATH问题。它是这样的:如果i=(G，u， u，k)是判定问题PATH的一个实例，那么若从u到v的最短路径的长度至多为k条边，则 PATH(i)=1(是)，否则PATH(i)=0(否)。许多抽象问题并不是判定问题，而是最优化问题，在这些问题中，某些量必须被最大化或最小化。然而，如我们在上面看到的，将最优化问题转化为一个“判定问题”通常并不困难。

编码

如果要用一个计算机程序来求解一个抽象问题，就必须用一种程序能理解的方式来表示问题实例。抽象对象集合S的编码是从S到二进制串集合的映射e。例如，我们都熟悉把自然数N={0，1，2，3，4，…}编码为串{0，1，10，11，100，…}。在这种编码方案中，e(17)=10001。看过计算机键盘上字符的表示法的人都会熟知ASCII码。在ASCII码中，A的编码为1000001。即使是一个复合对象，也可以把其组成部分的表示进行组合，从而把它编码为一个二进制串。多边形、图、函数、有序对、程序等都可以编码为二进制串。

因此，“求解"某个抽象判定问题的计算机算法实际上是把一个问题实例的编码作为其输入。我们把以二进制串集合为实例集的问题称为具体问题。如果当提供给算法的是长度为n=|i|的

一个问题实例i时，算法可以在O(T(n))时间内产生问题的解，我们就说该算法在时间O(T(n))内解决了该具体问题。因此，如果对某个常数k，存在一个能在O(r')时间内求解出某具体问题的算法，就说该具体问题是多项式时间可解的。

现在可以形式化地定义复杂类Р为在多项式时间内可解的具体判定问题的集合。

我们可以利用编码将抽象问题映射到具体问题上。给定一个抽象判定问题Q，其映射为实例集合Ⅰ到{0，1}，利用编码e:I→{0，1}*可以导出与该问题相关的具体判定问题，用e(Q)来表示◎。如果一个抽象问题实例i∈Ⅰ的解为Q(i)∈{0，1}，则该具体问题实例ei)∈{0，1}”的解也是Q(i)。在技术上，二进制串可能表示一组无意义的抽象问题实例。为了方便起见，假定任何这样的串都映射到0。因此，对表示抽象问题实例的编码的二进制串实例，具体问题与抽象问题产生同样的解。

我们希望通过编码的方式把多项式时间可解性的定义从具体问题扩展到抽象问题，但同时也希望这一定义与任何特定的编码无关，即求解一个问题的效率不应依赖于问题的编码。遗憾的是，实际上这种依赖性是相当严重的，例如，假定把一个整数é作为一个算法的唯一输人.并假设算法的运行时间为8(k)。如果提供的整数k是一元的(即由k个1组成的串)，那么对长度为n的输人，该算法的运行时间为多项式时间O(n)。但是，如果采用更自然的二进制来表示整数k，则输人长度为n=Llgk+1。在这种情况下，该算法的运行时间为8(k)=8(2")，它与输入规模成指数关系。因此，根据编码的不同，算法的运行时间是多项式时间或超多项式时间。

因此，对一个抽象问题如何编码，对理解多项式时间是相当重要的。如果不先指定编码，就不可能真正谈及对一个抽象问题的求解。然而，在实际应用中，如果不采用代价高昂的编码(如一元编码)，则问题的实际编码形式对问题是否能在多项式时间内求解的影响是微不足道的。例如，因为在多项式时间内，很容易将三进制表示的整数转化为二进制表示的整数，所以三进制代替二进制表示整数对问题是否能在多项式时间内求解没有任何影响。

对一个函数f:{0，1}"→{0，1}*，如果存在一个多项式时间的算法A，它对任意给定的输入x∈{0，1}，都能产生输出f(z)，则称该函数是一个多项式时间可计算的函数。对某个问题实例集，如果存在两个多项式时间可计算的函数fia和fa满足对任意i∈I，有f(e(i))=e(i)，且fa(e(i))=e()，我们就说这两种编码e和 e是多项式相关的9。也就是说，e(à)可以由一个多项式时间的算法根据编码e(i)求出，反之亦然。如果某一抽象问题的两种编码e和e是多项式相关的，则如下面引理所述，该问题本身是否是多项式时间可解与选用哪―种编码无关。

引理34.1设Q是定义在一个实例集Ⅰ上的一个抽象判定问题，e和e是Ⅰ上多项式相关的编码，则e,(Q∈P当且仅当ez(Q)EP。