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

34.4NP完全性的证明

通过直接证明对于任意语言L∈NP，都有L≤;CIRCUIT-SAT，我们可以证明电路可满足性问题是NP完全的。在本节中，我们将说明如何在不把NP中的每一种语言直接归约为给定语言的前提下，证明一种语言是NP完全的。我们将通过证明各类公式可满足性问题是NP完全问题来阐明这一方法。34.5节中提供了更多用于说明这一方法的更多例子。

下面的引理是证明一种语言是NP完全语言的方法的基础。

引理34.8  如果语言L是一种满足对任意L'∈NPC都有L'≤L的语言，则L是NP难度的。此外，如果L∈NP，则L∈NPC。

证明  由于L'是NP完全语言，所以对所有L"∈NP，都有L"≤_pL'。根据假设，L'≤_pL。因此根据传递性(见练习34.3-2)，有L"≤_pL，这说明L是NP难度的。如果L∈NP，则也有L∈NPC。

换句话说，通过把一个已知为NP完全的语言L'归约为L，就可以把NP中的每一种语言都隐式地归约为L。因此，引理34.8提供了证明某种语言L是NP完全语言的一种方法：

1.证明L∈NP。

2.选取一种已知的NP完全语言L'。

3.描述一种可计算函数f(x)的算法，其中f可将L'中每一个实例x∈{0，1}*映射为L中的实例f(x)。

4.证明函数f满足x∈L'当且仅当对于所有的x∈{0，1}都有f(x)∈L。

5.证明计算函数f的算法具有多项式运行时间。

(第2步到第5步说明了L是NP难度的。)这种根据一种已知的NP完全语言进行归约的方法，比说明如何直接根据NP中每一种语言进行归约这一复杂的过程要简单得多。证明CIRCUIT-SAT ∈NPC使我们有了一个立足点，由于已知电路可满足性问题是一个NP完全问题，因此现在可以更为简单地证明其他问题也是NP完全问题。而且，随着我们逐渐建立起一个已知NP完全问题的目录，选择根据哪一种语言进行归约的余地就更大了。

公式可满足性

对于确定布尔公式(而非电路)是否可满足这一问题，通过给出一个NP完全性的证明，来说明上面提到的归约方法。这一问题是我们已知历史上第一个被证明的NP完全问题。

我们根据语言SAT来形式化地定义可满足性问题，SAT的一个实例就是由下列成分组成的布尔公式Φ:

1.n个布尔变量：x₁，x₂ , …，x_n 。

2.m个布尔连接词：具有一个或两个输入和一个输出的任何布尔函数，如A(与)、V(或)、一(非)、→(蕴涵)、→(当且仅当)。

3．括号。(不失一般性，假定没有冗余的括号，即每个布尔连接符至多包含一对括号。)

很容易对一个布尔公式卢进行编码，使其长度是关于n+m的多项式。如在布尔组合电路中一样，关于一个布尔公式卢的真值赋值是为卢中各变量所取的一组值;可满足性赋值是指使公式卢的值为1的真值赋值。具有可满足性赋值的公式就是可满足公式。可满足性问题提出如下问题:“一个给定的布尔公式是不是可满足的?”用形式语言的术语来表达，就是:

SAT={<Φ>:Φ是一个可满足的布尔公式}

例如，公式

Φ=((x₁→x₂) V￢((￢x₁↔x₃) V x₄))Λ￢x₂

具有可满足性赋值<x₁=0，x₂=0，x₃=1，x₄=1>，因为

Φ=((0→0) V￢((￢0↔1)V 1))Λ￢0 = (1V ￢(1 V 1))Λ1

=(1 V 0)Λ1 =1

(34.2)

因此,该公式Φ属于SAT。

“确定一个任意的布尔公式是否是可满足的”这一问题没有多项式运行时间的朴素算法。在一个具有n个变量的公式中，有2ⁿ种可能的赋值。如果<Φ>的长度是关于n的多项式，则检查每一种赋值需要Ω(2ⁿ)时间，这是<Φ>长度的超多项式。正如下面定理所述，此时，不太可能存在多项式时间的算法。

定理34.9  布尔公式的可满足性问题是NP完全的。

证明  首先证明SAT∈NP，然后通过证明CIRCUIT-SAT≤_pSAT，来证明SAT是NP难度的；根据引理34.8，这将证明定理成立。

为了证明SAT属于NP，我们来证明对于输入公式Φ，由它的一个可满足性赋值所组成的证书可以在多项式时间内得到验证。验证算法将公式中的每个变量替换为其对应的值，再对公式进行求解，这一做法与式(34.2)的做法非常类似。这一任务很容易在多项式时间内完成，如果表达式的值为1，则算法得到验证，此表达式是可满足的。因此，引理34.8中有关NP完全性的第一个条件就成立了。

为了证明SAT是NP难度的，首先来证明CIRCUIT-SAT≤_pSAT。换句话说，我们需要证明的是，电路可满足性问题的任何实例可以在多项式时间内归约为公式可满足性问题的一个实例。利用归纳法，可以将任意布尔组合电路表示为一个布尔公式。观察一下产生电路输出的逻辑门，并归纳地将每个逻辑门的输入表示为公式。于是，通过写出一个表达式，将逻辑门的功能作用于其输入的公式，即可获得与电路对应的公式了。

遗憾的是，用这种直接的方法并不能构成一个多项式时间的归约过程。如练习34.4-1所要求的，证明共享的子公式(它们源自于那些输出线的扇出为2或更多的逻辑门)会使得所生成的公式的规模呈指数增长。因此，从某种意义上来说，我们采用归约算法是更明智的。

图34-10利用图34-8(a)中的电路说明了我们该如何克服这一问题。对电路C中的每一根线x_i，公式Φ中都有一个变量x。我们现在可以说明如何将逻辑门操作表示为关于其附属线路变量的公式。例如，输出“与”门的操作为x₁₀←→(x₇A x₈Ax₉)。我们把这些附属公式称为子句。

此归约算法产生的公式为Φ，它是电路输出变量与描述每个门操作的子句合取式的“与”。对图中的电路，相应的公式为:

Φ=x₁₀Λ（x₄↔￢x₃）

Λ（x5↔（x₁ V x₂））

Λ（x₆↔￢x₄）

Λ（x7↔（x₁ Λ x₂ Λ x₄））

Λ（x8↔（x₅ V x₆））

Λ（x9↔（x₆ V x₇））

Λ（x10↔x₇ Λ x₈ Λ x9））

给定一个电路C，就可以直接在多项式时间内产生这样的一个公式Φ。

为什么只有当公式Φ可满足时，电路C才是可满足的呢?如果C具有一个可满足性赋值，那么电路的每条线路都有一个良定义的值，并且电路的输出为1。因此，用线路的值对中的每个变量赋值后，就使得Φ中每个子句的值为1，因而，所有子句的合取值也为1。反之，如果存在一个赋值Φ的值为1，则类似可证电路C是可满足的。这样就证明了CIRCUIT-SAT≤_pSAT，从而问题得证。