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

34.3NP完全性与可归约性

从事理论研究的计算机科学家们之所以会相信P≠NP，最令人信服的理由就是存在着一类“NP完全”问题。该类问题有一种令人惊奇的特质，即如果任何一个NP完全问题能在多项式时间内得到解决，那么，NP中的每一个问题都存在一个多项式时间解，即P=NP。但是，尽管经过了多年的研究，目前仍没有找出任何NP完全问题的多项式时间算法。

语言HAM-CYCLE就是一个NP完全问题。如果我们能够在多项式时间内判定 HAM-CYCLE，就能够在多项式时间内求解NP中的每一个问题。事实上，如果能证明NP一Р为非空集合，就可以肯定地说HAM-CYCLE∈NP一P。

在某种意义上说，NP完全语言是NP中“最难”的语言。在本节中，我们将说明如何运用称为“多项式时间可归约性”的确切概念，来比较各种语言的相对“难度”。首先，我们先正式定义NP完全语言，然后，再简要地证明一种称为CIRCUIT-SAT的语言是NP完全的。在34.4节和34.5节中，将运用可归约性概念来证明许多其他问题都是NP完全的。

可归约性

从直觉上看，问题Q可以被归约为另一个问题Q'。如果Q的任何实例都可以被“容易地重新描述"为Q'的实例，而Q'的实例的解也是Q的实例的解。例如，求解关于未知量α 的线性方程问题可以转化为求解二次方程问题。已知一个实例ax+b=0，可以把它变换为0r+ar+b=0，其解也是方程ax十b=0的解。因此，如果一个问题Q可以转化为另一个问题Q'，则从某种意义上来说，Q并不比Q'更难解决。

回到关于判定问题的形式语言体系中。我们说语言L在多项式时间内可以归约为语言L，记作L₁≤_PL₂，如果存在一个多项式时间可计算的函数f:{0，1}*→{0，1}*，满足对所有的x∈{0，1}”,

x∈L₁当且仅当f(x)=L₂(34.1)则称函数f为归约函数，计算f的多项式时间算法F称为归约算法。

图34-4通过归约函数f，在多项式时间内将语言L₁归约为语言L₂。

对任何输入x∈{0，1}*，是否有x∈L₁这一问题与是否有f(x)∈L₂的答案是一样的

图34-4说明了关于从语言L到另一种语言L的多项式时间归约的思想。每一种语言都是{0，1}*的子集，归约函数f提供了一个多项式时间的映射，使得若x∈L，则fz)∈L。而且若α∈≠L，则f(z)4L。因此归约函数提供了从语言L表示的判定问题的任意实例α到语言L₂表示的判定问题的实例f(x)上的映射。如果能提供是否有f(x)∈L₂的答案，也就直接提供了是否有x≠L₁的答案。

多项式时间归约为证明各种语言属于Р提供了一种有力的工具。

引理34.3 如果L_1,L₂C{0，1}*是满足L₁≤_pL₂的语言，则L₂∈P蕴涵着L₁∈P。

证明 设A₂是一个判定问题L₂的多项式时间算法，F是计算归约函数f的多项式时间归约算法。下面来构造一个判定L的多项式时间算法A₁。

图34-5说明了A₁的构造过程。对给定的输入x∈(0，1}*，算法A₁利用F把x变换为f(x)，然后它利用A₂测试是否有f(x)∈L₂。A₂的输出值提供A₁作为输人，并产生答案作为输出。

根据条件(34.1)可以推导出A₁的正确性。因为F和A₂的运行时间都是多项式时间，所以该算法的运行时间为多项式时间(参见练习34.1-5)。