计算机算法基础 第2版 课件 第14章 NP-完全问题

1第14

章

NP-完全问题序言

2预备知识

4P和NP语言类

20NPC语言类和NPC问题

29第一个NPC问题

32若干著名NPC问题的证明

431.序言2有些看似容易的问题找不到多项式算法。例如，在图中找一条两点间最长的简单路径。不论k多大，都找不到O(nk)的算法。这引起人们对问题本身固有的难易程度的探讨兴趣，也是这一章讨论的课题。问题分类。有多项式算法的问题称为可驾驭的(tractable)问题，或称为容易问题，否则称为不可驾驭的(intractable)问题，或难问题。NP完全问题(NP-complete问题，简称NPC问题)简单说，是至今还无法判断属于容易问题，还是难问题的一类问题。为了理解NPC问题，我们将先介绍P类和NP类问题。3P类问题有多项式算法的问题属于P类。也可认为，在一个确定的图灵机上有多项式算法。(后面会定义图灵机)NP类问题在非确定的图灵机上有多项式算法的问题属于NP类。许多难以判断的问题都属于这一类，例如哈密尔顿回路问题、最小顶点复盖问题、图的三着色问题等。NPC类问题NPC类是NP类中最困难的问题，NPC

NP。如果NPC中有一个有多项式算法，那么所有NP问题都有多项式算法。反之，如有一个没有多项式算法，那么所有NPC问题都没有多项式算法。P

NP猜想已证明PNP，猜想PNPC=，即P

NP，但至今未能证明。4图灵机图灵机TM，通常指确定的图灵机(DeterministicTuringMachine)，是一个简单的计算模型。10B101BB

有限状态控制器(q,a)(q’,a’,D)2.预备知识由一个有限状态控制器和一条右端无限长的读写带组成。读写带从左到右划分为无限多个连续的方格，每个方格可存放字符集

中的一个符号。空白的格子由特殊符号B表示。Q是个有限个状态的集合。有限状态控制器在任一时刻处于Q中的一个状态q并控制读写头的读写操作。一开始在初始状态q0。(接下页)5如果有限状态控制器当前的状态是q

Q，其读写头正在扫描的字符是a

，那么，有限状态控制器做三件事：更改下一时刻的状态为q’

更新所扫描的字符为a’决定读写头向左(L)移动一个方格，或向右(R)移动一个方格，或停留不动(N)。上述三件事都是确定好的，可以表示为(q,a)

(q’,a’,D)，或者

(q,a)=(q’,a’,D)，这里D可以是L，R，或者N。

称为状态转换函数，允许q’=q

和a’=a。因为集合Q和

都是有限集合，

(q,a)转換函数可以用一个有限长的表格表示。集合Q有子集F

Q，子集F

中的状态称为终止状态。第13章的有限状态自动机是图灵机的特殊情况。它不改变读写带上的字符，没有输出值，停机在接收状态表示接收输入字符串。6图灵机计算一个函数或识别一个字符串的过程开始时，输入数据或字符串从左边第一个方格开始放在读写带上，图灵机处在开始状态q0，而读写头指向第一个方格。·然后，根据转換函数不断地变更状态、修改符号、和移动读写头。当进入了一个终止状态qf

F时，计算停止。这时，在带子上的字符串或在某些指定格子上符号就是输出的函数值。如果用来识别一个字符串，可以输出一个特定符号(比如1)表示接收这个字符串，输出另一特定符号(比如0)表示拒绝这个字符串。图灵机有可能永远不能进入终止状态，这时我们说函数对输入数据无定义或者说图灵机对输入字符串不能判定。图灵机的计算复杂度定义为其状态转换的次数T(n)，这里n是输入字符串的长度，并且只对停机的情况才考虑复杂度。7符号集和编码对计算复杂度的影响用不同的符号集合会影响输入规模的大小。比如整数98，用十进制，只要两个符号9和8表示；如果用2进制，98=11000102则需要7个符号表示；如果用1进制，则需要98个0表示。设某图灵机T使用的符号集是

，|

|=d，d

2。现在假设有另一个图灵机T’，它做一次状态转换所需时间与T相同，但字符集

’与

不同，|’

|

2。我们可用

’中两字符a和b(可视为0和1)来对

中每个字符编码，长为k=

lgd

。这样一来，对

中一个字符的操作变成了对一个长为k的序列的操作。因为d和k都是常数，图灵机T’的渐近复杂度与T的相同。所以，除一进制的编码外，用不同的符号集不影响算法的复杂度。为方便起见，以下讨论中，我们就假定

={0,1}。8判断型问题和优化型问题及其关系如果一个问题的答案只有两种，是(yes)或不是(no)，则称为一个判断型问题。例如，判断一个图是否有一条哈密尔顿回路就是一个判断型问题。一个问题被称为优化型问题，如果这个问题的解对应于一个最佳的数值，例如在图中找一个最短路径。不同的优化型问题有着不同的优化目标和量纲。例如，要求解必须是最长、最短、最大、最小、最高、最低、最重、或最轻等等。不便于讨论不同问题之间的关系。讨论NP完全问题时，我们限定所有被分类的问题都是判断型问题。这一简化使我们可以讨论任何两个判断型问题之间的关系。只要两个问题的解都是yes，则可认为它们有同解。这对NP完全问题的研究起着奠基性的关键作用。(接下页)9判断型问题和优化型问题及其关系(继续)只限于判断型问题的讨论不会影响NPC理论的应用价值，因为一个优化型问题往往可对应于一个判断型问题。而且，如果对应的判断型问题有多项式算法，那么其对应的优化型问题也往往有多项式算法。下面看一个例子。例14.1一个优化型问题定义如下：给定一个连通的无向图G(V,E)以及V中两顶点s和t，找出一条从s到t的简单路径使得它含有的边最多。为上述优化问题定义一个对应的判断型问题；假设(a)中的判断型问题有多项式算法A，以算法A为子程序，设计一个多项式算法来解决对应的优化问题。解：(a) 我们引入一个变量k后，这个判断型问题可定义如下：给定连通的无向图G(V,E)和正整数k，以及V中两顶点s和t，是否存在一条含至少k条边的从s到t的简单路径？(接下页)10例14.1解(继续)(b) 优化型问题的算法如下。第一步确定最长路径的边的个数k。第二步测试每条边。如果刪去这条边后，图中仍有长为k的路径，则刪去，否则保留。每条边都测试后，剩下的边必定形成一条长为k的路径。设(a)的多项式算法为A(G,s,t,k)，算法伪码如下：Longest-path(G(V,E),s,t)k

n-1whileA(G,s,t,k)=no；

k

k-1；endwhile；

//最长路径有k条边G’(V’,E’)

G(V,E) //复制一个G(V,E)，V’=V，E’=Eforeache

E’ E’

E’–{e} //从E’中刪去e ifA(G’,s,t,k)=no //如果G’中不再存在长为k的路径

thenE’

E’

{e} //把e放回来 endifendforreturn

G’End11判断型问题的形式语言表示给定字符集

，它的所有字符串的集合，包括空串

，称为

的全语言，记为

*。例如，

={0,1}，

*={

,0,1,00,01,10,…}。给定字符集

，它的全语言的一个子集L

*称为定义在

上的一个语言。换句话说，任何一个

上的字符串的集合称为一个语言。我们只对有意义的语言感兴趣，例如，L={10,11,111,1011,…}代表所有质数的集合。一个“问题”

是一个抽象的定义，它由许许多多的实例所组成。比如，“哈密尔顿回路问题”包含了所有图的哈密尔顿回路问题。对一个具体的图来讲，比如图8-1(a)，它是否有哈密尔顿回路的问题，是“哈密尔顿回路问题”的一个实例。一个实例，也必须是一个实例才可以用一个0和1的字符串x表示。(接下页)12判断型问题的形式语言表示

(继续)反之，给定一个子符串x，可以有三种情况：x代表问题

的一个实例并且有答案yes；x代表问题

的一个实例并且有答案no；x不代表问题

的一个实例，而是一个杂乱的子符串。用

(x)=1表示

第1种情况，用

(x)=0表示

第2,3种情况。给定一个判断型问题

，它对应的语言L(

)是有yes答案的所有实例的子符串的编码的集合：

L(

)={x|x

*and

(x)=1}。例如，哈密尔顿回路问题对应的语言可表示为： Hamilton-Cycle={<G>|G含有哈密尔顿回路}。这里，Hamilton-Cycle是这个语言的名字，而<G>是对一个实例，图G，的编码的字符串。13判断型问题的算法解一个判断型问题

的算法A所做的事就是对任何一个输入字符串x

*进行扫描和运算，然后输出答案A(x)。答案的形式有：A(x)=1

表示接收x，A(x)=0

表示拒绝x，和不回答，

表示不能判定x。所以，解一个判断型问题

的算法就等价于一个识别语言L(

)的算法。也就是识别任一给定字符串x是否有x

L(

)。我们把这样的算法称为判断型算法。为简便起见，除非特别说明，本章讨论的问题和算法都是指判断型问题和算法。14定义14.4

给定一个算法A，所有被A所接收的子符串的集合，L={x|A(x)=1}，称为被A所接收(Accepted)的语言。进一步，如果A对其他的子符串都拒绝，即

y

L，A(y)=0，则称语言L被A所判定(Decided)。定义14.5

给定一个问题

，如果它对应的语言L(

)正好等于被算法A所接收的语言，那么称问题

或语言L(

)被A所接收。如果问题

对应的语言L(

)正好等于被算法A所判定的语言，那么称问题

或语言L(

)被A所判定。显然，给定问题

，如果能找到算法A使L(

)被A所判定，那么我们就解决了这个问题。但是，重要的问题是算法A的复杂度。给定一个问题

，我们总是希望找到一个复杂度小的算法来判定，至少是有多项式的复杂度，但往往不容易。下面讨论复杂度问题。15多项式关联两个计算模型T1和T2称为多项式关联的，如果对任一个判断型问题，T1上存在一个多项式复杂度的判定算法，当且仅当

T2上存在一个多项式复杂度的判定算法。显然，如果计算模型T1和T2是多项式关联的话，那么在我们讨论一个问题是否有多项式算法时，用哪一个计算模型都不影响这个问题的结论。因为图灵机和其他现代计算机的抽象模型被证明都是多项式关联的，所以我们可随意用其中的一个模型来讨论。下面，如不加说明，我们用的是图灵机的模型。16多项式归约定义14.6

给定两个语言L1和L2，如果存在一个算法f，它把

*中每一个字符串x转换为另一个字符串f(x)，并且满足：x

L1

当且仅当f(x)

L2；f是个多项式算法，即转换在O(|x|c)的时间内完成，这里c是一个正数常数；那么，我们说L1可多项式归约到L2，记为L1

p

L2，并称f为多项式转换函数或算法。多项式归约中转换函数f把

*中每一个字符串映射到另一个字符串。这个映射不要求单射(onetoone)，也不要求满射(onto)，但一定要把L1

内的一个字符串映射到L2

内的一个字符，把L1

外的一个字符串映射到L2

外的一个字符串。下图(14-2)解释了这个映射关系。17图14-2定义14.7 假设问题

1和

2对应的语言是L(

1)和L(

2)。如果语言L(

1)可多项式归约到语言L(

2)，则称问题

1可多项式归约到问题

2，记为

1

p

2。从问题的角度看，

1

p

2意味着

1的任何实例x被一多项式转换算法f变为

2的一个实例f(x)并且

1(x)=yes

当且仅当

2(f(x))=yes。18定理14.1

如果L1

p

L2，而语言L2可被一多项式算法A2所判定，那么必存在一个多项式算法A1使语言L1被A1所判定。证明：

如下图(14-3)所示，我们可这样设计A1:对任一个字符串x，A1先用多项式转换函数f把x转换为f(x)，然后让算法A2去判定。如果A2(f(x))=1，则输出A1(x)=1，否则有A2(f(x))=0，则输出A1(x)=0。由于f(x)

L2

当且仅当x

L1，所以算法A1可正确地判定语言L1。(接下页)算法fxf(x)A2yes,f(x)

L2yes,x

L1no,x

L1no,f(x)

L2A1图14-319注评：如果问题

1可多项式归约到问题

2，那么从多项式可解的角度看，问题

2可认为比

1更难，因为找到

2的多项式算法就可以有

1的多项式算法。如果问题

2也可以多项式归约到问题

1，那么我们认为两者在多项式可解上等价。证明

(继续)算法A1所用的时间是由两部分组成，第一部分是把x转换为f(x)的时间t1，第二部分是算法A2判定f(x)的时间t2。设|x|=n，因f是多项式转换函数，不妨设

t1

<nc，这里c是一个大于0的常数，并且有|f(x)|

nc，这是因为在nc步时间内，算法不可能产生多于nc个字符。

又因为算法A2是个多项式算法，所以t2<|f(x)|k

≤

nck，这里k也是一个正的常数。因此t1+t2=O(nc+nck)，算法A1是个多项式算法。

20上一节把问题

对应于

={0,1}上的一个语言L(

)。因此，对问题的分类也就是对语言的分类。P语言类定义14.8

P语言类(classP)是可以在多项式时间内被算法判定的语言的集合，即P={L|L

*可被一多项式算法所判定}。如果

对应的语言L(

)属于P类，那么问题

也称为P类问题。定理14.2

如果语言L可以被一个算法在多项式时间内接收，那么L就可以被一个算法在多项式时间内判定。证明：如果L可被算法A在多项式时间内接收，那么存在c>0，使得对任一字符串x

L，算法A在|x|c步内输出A(x)=1。所以，如果x

L，那么算法A会在|x|c步内输出A(x)=0或者不做判定。(接下页)3.P和NP语言类

21证明(继续)：如果算法A在|x|c步内不做判定，则表明x必定不属于L。所以，既使算法A在|x|c步内不做判定，x

L的结论已可做出。所以，我们可以设计算法B，对任一输入字符串x，它在|x|c步内和算法A的动作完全一样，而在|x|c步之后，如果A还没有做出判定，则输出B(x)=0。显然语言L可以被算法B在多项式时间内判定。

非确定图灵机(non-deterministicTuringmachine)与确定的图灵机的唯一区别就是状态转换函数

。在确定的图灵机中，

把(q,a)映射到唯一的三元组(q’,a’,D)。在非确定的图灵机中

把(q,a)映射到多个三元组的一个集合，即

(q,a)={(q1,a1,D1)，(q2,a2,D2)，…，(qk,ak,Dk)}，这里k是个正整数常数。确定的图灵机可看作非确定的图灵机的一个特例。22用非确定的图灵机T识别语言与确定的图灵机操作一样，它从初始状态q0开始，如果当前状态是q，当前扫描的字符是a，它要决定三件事，即下一个状态q’，更新的字符a’，和读写头的移动D。它可以任意选择集合

(q,a)中的一个三元组来变换状态，更新字符，和移动读写头。当T进入一个接收状态，输出1，并停止运算，表示输入字符串x被T接收(T(x)=1)。这种情况下，如果我们把非确定的图灵机T每步选择的三元组按序记录下来的话，这个序列称为x的一个计算路径。可能有多条，最短的一条计算路径的长度定义为接受x的时间复杂度。只要存在一条x的计算路径，可假定这个非确定的图灵机每一步都沿最短的一条计算路径正确地选择集合

(q,a)中的一个三元组。23定义14.9 一个语言L称为是被非确定的图灵机T在多项式时间内接收的语言，如果它满足：每一个x

L都可以被T在多项式时间内接收，即存在一条计算路径，其长度

|x|c，这里，c>0是一个固定的常数。每一个被图灵机T在多项式时间|x|c内接收的字符串x都属于语言L，x

L。定义14.10NP语言类(classNP)是所有可以被非确定的图灵机在多项式时间内接收的语言的集合，即:NP={L

|L

*并且L

可被一非确定的图灵机在多项式时间内接收}。

如果问题

对应的语言L(

)属于NP类，那么问题

称为NP类问题。24定理14.3 P

NP。证明：因为一个确定的图灵机可看作一个非确定的图灵机的一个特例，只是它的转换函数

(q,a)只含单个三元组，所以有P

NP。

多项式检验算法和NP类语言证明L属于NP类时，需要设计一个非确定的图灵机，很不方便。一个与之等价的计算模型是多项式检验机(polynomialverifier)。在检验机的输入字符串中，除字符串x以外，还有一个字符串y，其长度|y|是|x|的多项式函数。字符串y是用来证明x

L的。如果x

L，不可能有字符串y。如果x

L，则一定有字符串y。字符串y称为“证书”(certificate)。如果我们把x和y合起来看作输入字符串的话，T就是一个确定的图灵机。当这个检验机T对输入字符串x和y进行运算后输出T(x,y)=1，我们说T接收字符串(x,y)。25定义14.1一个语言L称为一个多项式时间可检验的语言，如果存在一个(确定的)图灵机T使得x

L

当且仅当存在一个字符串y，|y|≤|x|c,使得字符串(x,y)被T在多项式时间内所接收，即T(x,y)=1。这里，c是一个固定的正数常数，y称为x的证书，而T称为L的多项式检验机。显然，如果把|y|和|x|总长看为输入规模n’

的话，那么一个n’的多项式函数也必定是n

的多项式函数。不难证明多项式检验机的模型与非确定图灵机等价，即一个多项式时间可检验的语言必定可以被一个非确定图灵机在多项式时间内接收，反之亦然。我们略去证明。由于等价，一个NP类语言L也就是一个多项式时间可检验的语言，反之亦然。26NP-算法(多项式检验算法)确定的图灵机与现代计算机模型多项式关联。如果有一个现代计算机的算法A，使得x

L

当且仅当存在一个字符串y，|y|≤|x|c,使字符串(x,y)被A在多项式时间内所接收，那么L就是一个多项式时间可检验的语言，算法A称为L的多项式检验算法，或NP-算法。如果问题

对应的语言L(

)有NP-算法，那么

也就属于NP类了，所以，在证明

是NP类问题时，我们只要设计一个多项式检验算法A去接受L(

)即可。在设计NP算法时，我们要设计证书y并证明，这样的证书y存在当且仅当

(x)=yes，并给出多项式检验步骤即可。当

(x)=no时，证书y不存在，对任何附加输入y，检验算法输出A(x,y)=0或no或不回答。下面我们看2个例子。(见下页)27例14.2证明有向图G(V,E)是否有哈密尔顿回路的判断问题属于NP类。证明：如果G(V,E)有哈密尔顿回路，它通过每个顶点正好一次，那么我们可以把这个回路作为证书来验证。显然，如果G(V,E)有哈密尔顿回路，这个证书是存在的。我们用p表示有n个顶点的序列并作为输入的证书。多项式检验算法的伪码如下：Hamilton-Cycle-Verification(G(V,E),p) //x

=G(V,E),y=p检查是否有|p|=|V|检查p

中每个顶点是否属于集合V检查V中每个顶点是否在p中出现，并且只出现一次检查从p中每个顶点到下个顶点是否是E中一条边检查从p的最后一个顶点到p的第一个顶点是否是E中一条边如果第1步到第5步的答案都是yes，那么输出1，否则输出0End28

29简单来讲，NP完全(NPC)问题就是NP类中最难的问题。如果有一个NPC问题有多项式算法，那么所有NP类问题都会有多项式算法。定义14.12一个语言L被称为NPC语言，如果它满足：(1)L

NP;

(2)NP类中任何一个语言L’可多项式归约到L，即L’

p

L。註评:如果一个语言L只满足第2个条件，那么L被称为一个NP难(NP-hard)语言。如果一个问题

所对应的语言L(

)是NPC或NP难语言，那么问题

则对应地被称为是一个NPC问题或NP难问题。一个NPC问题显然也是一个NP难问题。定义14.13

NPC语言类是所有NPC语言的集合，简记为NPC。即: NPC={L|L

是一个NPC语言}。通常，NPC也用来代表所有NPC问题的集合3.NPC语言类和NPC问题

30定理14.4

任何一个NPC语言有多项式判定算法当且仅当P=NP。证明：如果某个NPC语言L有多项式算法来判定，那么L

P。又因为L

NPC，任何一个NP语言L’可以多项式归约到L，即L’

p

L，由定理14.1，L’可以被一个多项式算法所判定，所以有L’

P。这就意味着NP

P，但由定理14.3，P

NP，所以得到P=NP。反之，如果有P=NP，那么因为NPC

NP=P，所以任何一个NPC语言L有多项式算法判定。

推论14.5

如果一个NPC语言L没有多项式算法，那么P

NPC=

。证明：为用反证法，我们假设L没有多项式判定算法，但是P

NPC

。那么必有一语言L’

P

NPC。这表明L’有多项式判定算法并且属于NPC。从定理14.4知，P=NP，所以L

NPC

NP=P。那么，L也必定有多项式算法，这与“L没有多项式算法”矛盾。

31P、NP、和NPC之间可能的关系到目前为止，人们还不知道是否有一个NPC语言L可以被一多项式算法所判定，也不能证明任何一个NPC语言L不可能被一多项式算法所判定。因此，如下图(14-4)所示，集合P，NP，和NPC之间的关系有两种，但大部分人相信第二种(图14-4(b))，但有待证明。PNPNPC(a)P=NPC=NPP=NPC=NP(b)P

NPC=

32第一个NPC问题历史上第一个被证明的NPC问题是布尔表达式的可满足性问题。一个布尔表达式就是用逻辑运算把布尔变量连结起来的表达式，例如，

=((x1

x2)

((

x1

x3)

x4))

(

x2

x3)。如有一组变量的赋值使表达式

=1，则称该表达式是可被满足的。例如，若赋以x1=0，x2=0，x3=1，x4=1，则上面表达式的值为:

=((x1

x2)

((

x1

x3)

x4))

(

x2

x3)=((0

0)

((

0

1)

1))

(

0

1)=(0

(1

1))

(1

1)=(0

1)

1=1。

所以上面例子中表达式是可以被满足的。

如果不论怎样给变量赋值，表达式的值总是为0，那么称该表达式为不可被满足。例如

=(x1

x2)

x1

x2

就是一个不可被满足的布尔表达式。33布尔表达式的可满足性(FormulaSatisfiability)问题，简称为SAT问题，就是判断任一个给定布尔表达是否可被满足。StephenCook在1971年证明了SAT问题是个NPC问题，称为Cook定理。这个定理有着划时代的意义，因为它证明了在NP类中确实存在象SAT这样的NPC问题，而且而且大大地简化了证明和发现其他的NPC问题的工作，现在，当我们需要证明一个新的问题

是NPC问题时，只需遵循下面的方法。新问题

是NPC问题的证明步骤:证明

NP选一个已被证明的NPC问题

’并证明

’

p

。正确性：因为

’

NPC，所以NP类中任一个问题

’’可多项式归约到

’，即

’’

p

’。又因为

’

p

，所以

’’也可多项式归约到

，

’’

p

，尽管这个归约需要二步。

34Cook定理的证明比较长，我们略去这个证明，但是我们选用另外一个NP类问题作为第一个NPC问题来证明。电路的可满足性问题(Circuit-SAT)考虑组合电路C，它由与门、或门、和非门组成。电路C有若干个输入信号，每个信号可取0或1。当一组输入信号经过电路C后，电路产生一个0或1的输出信号。如果有一组输入信号(输入变量)使得输出信号的值是1，那么这个电路被称为可满足的，否则为不可满足。电路的可满足性问题就是对任一给定电路C，判断它是否可满足。用<C>表示电路C的一个字符串编码，那么，电路的可满足性问题对应的语言可定义为

Circuit-SAT={<C>|电路C可被满足}。下图(14-5(a)和(b))分别给出了一个可满足和不可满足的电路实例。35x31x1x211111110(a)

一个可满足的电路实例x1x2x3(b)

一个不可满足的电路实例定理14.6

语言Circuit-SAT属于NPC类。证明：我们先为语言Circuit-SAT设计一个NP算法。每个逻辑门只有一个输出值并且是其它门的输入，我们把它们之间的连接称为一根连线。当输入变量给定时，每条连线上的二进制值及C的输出值就定了。假设x是电路C的编码，其长度|x|与输入变量的个数，逻辑门的个数，及连线的个数的总和成正比(或多项式函数)。电路C满足时，证书y包含所有连线，所有输入和输出变量上的二进制值。显然有c

>0使|y|≤|x|c。NP-算法如下:(见下页)36定理14.6 的证明(继续1)Circuit-SAT-Verification(<C>,y)1 对x=<C>中描述的每个门g做如下操作:1.1 在y中找出g的所有输入值和它的输出值1.2 检查门g的输入值和输出值之间的关系是否符合门g的定义1.3 如果不符合门g的定义，则输出0后退出算法，否则继续2 在y中找出C的输出值并检验是否为13 如果C的输出值是1，则输出1，否则输出0End显然，这个算法中每一步都可以在多项式时间内完成，因此，语言Circuit-SAT属于NP类。下面证明Circuit-SAT满足NPC的笫2个条件。证明任何NP语言L

可以多项式归约到语言circuit-SAT。(接下页)37定理14.6 的证明(继续2)因为L

NP，则有多项式检验机T对字符串x和证书y进行识别判断。设x=x1x2…xn，y=y1y2…ym，m

≤nc。x

L当且仅当T在M=(n+m)k步内可输出1。这里，k是一个常数。假设检验机T的读写带上的格子从0开始编号，这n+m个输入字符放在从0到n+m-1的格子中。其余的格子(从m+n

到M)中初始放0。假设输出符号t放在编号为n+m的格子中。因为T在M

步内停机，它不会扫描到第M号格子之后的格子。我们证明，可以在多项式时间内构造一个Circuit-SAT的实例C

使得检验机T在M

步内输出1当且仅当C

可被满足。(A)

我们先为电路C构造输入变量如下：(A.1)构造M=(n+m)k个输入变量，u0,u2,…,uM-1，顺序对应T上的头M个格子上字符。(接下页)38定理14.6 的证明(继续3)(A.2)构造r=

lgM

个额外的输入变量v1,v2,…,vr。二进制数v[1..r]=<v1,v2,…,vr>

指出当前读写头的位置，即地址，初始值为0。(A.3)假设T有W个不同状态，q0，q1，q2，…，qW-1，则构造d=

lgW

个输入变量，w1,w2,…,wd。二进制数W[1..d]=<w1,w2,…,wd>表示当前状态，初始值为0，初始状态为q0。W是常数，d为常数。(A.2)和(A.3)构造的输入变量是内部用的，输入值是固定的。(B) 对检验机T的每一步，构造一层电路，使得各变量通过后变化如下：(a)<u0,u1,…,uM-1>

等于检验机T一步操作后读写带上应有的值；(b)<w1,w2,…,wd>

等于检验机T

一步操作后新的状态；(c)<v1,v2,…,vr>

等于检验机T

一步操作后新的地址。所以，每层的输出变量的个数和含义与输入变量相同，但数值不同。这一层的构造是通用的，一共构造M层。图(14-6)显示了第一层的构造。见p41，具体解释如下。39定理14.6 的证明(继续4)

在u0,u1,…,uM-1中选取地址为k=v[1..r]

的变量uk(0

k

M-1)。设

uk

=a(0或1)。地址

k

对应当前读写头所指的读写带上格子的编号。变量a就是这个格子里的字符。如图，这可以用多路复用器(MUX)实现，需要的逻辑门和连线的个数是O(M)。MUX把变量a从地址

k取出后送到图左边的电路E。(2) 由变量a以及状态q的变量W[1..d]，电路

E计算检验机T的转换函数

(q,a)=(q’,a’,D)中三元组的三个函数值：(2.1) (q’,a’,D)中的a’。从(q,a)到a’的函数对应一个真值表，可用门电路来实现，含在电路E中，并且逻辑门和连线的个数是常数。图中

是输出信号。

=1表示a’=

(a)，而

=0表示a’=a。

通过DEMUX电路到达原地址k的位置，与输入信号

a会合于一个MUX。(接下页)40定理14.6 的证明(继续5) MUX根据

=1或

=0，输出a’=

a或a’=

a。这个MUX需要的逻辑门和连线个数是常数。DEMUX需要的逻辑门和连线的个数是O(M)。(2.2) 计算(q’,a’,D)中的状态q’

设q’=W[1..d]=<w’1,w’2,…,w’d>，我们为每个输出变量w’1,w’2,…,w’d分别构造一个真值表。每个真值表可以用门电路来实现，并且所用逻辑门和连线的个数也是常数。q’=<w’1,w’2,…,w’d>由电路E直接输出到下一层电路。(2.3) 三元组(q’,a’,D)中的D。这一步计算新地址，由原地址减1，或加1，或加0得到，分别对应

D=L，R，N。所以，D有两个比特，输出给一个MUX来做出选择。计算D需要的逻辑门和连线个数与d+1成正比，是常数。这个MUX需要的逻辑门和连线个数与r=

lgM

成正比。原地址减1，加1，或加0的计算需逻辑门和连线的个数也是O(r)。(接下页)4101MUXu101MUXuM-101MUX

uM-1u0u1MUX由状态转换函数得到真值表后构造的电路Ew1

w2…wd(初态=q0)aDEMUX

w’1

w’2…w’du0v1

v2…vr0rr+1-1MUX更新值

0122信号Dv’1

v’2…v’r图14-6

电路的第一层构造示意定理14.6 的证明(继续6)新地址的

r个变量<v’1,v’2,…,v’r>由这个MUX输出给下一层电路42定理14.6 的证明(继续7)

其余M-1层与第一层的构造相同，输入状态和地址由上一层的输出得到。另外，如当前状态是终止状态qf时，对任何输入变量a，规定

(qf,a)=(qf,a,N)。也就是说保持所有变量不变(C) 构造了M层电路后，再造一层电路以输出变量un+m。这只需O(n+m)个逻辑门和连线。下图(14-7)显示了最后一层构造。w1

w2…wd

v1

v2…vru0

u1…un+mun+m+1

un+m+2…uM-1t输出变量

1从上述构造可知，该电路忠实地摸拟检验机T的检验过程。所以，检验机T在M步内输出1当且仅当所构造电路可被满足。因为整个电路所含的逻辑门的个数或导线个数的总和不超过O(M2)，所以有L

p

Circuit-SAT。

43若干著名NPC问题的证明这一节我们介绍若干个早期被证明的最著名的NPC问题。下图(14-8)标出了我们要讨论的NPC问题以及与之关联的归约树。因为证明这些问题属于NP类很容易，我们只证明多项式归约部分。Circuit-SATSAT3-SATCliqueVertex-CoverHamilton-CycleTSPSubset-SumSet-Partitionk-Colorability44若干著名NPC问题的证明顺序circuit-SAT

pSAT 45SAT

p3-SAT 473-SAT

pclique 51clique

pvertex-cover 55vertex-cover

pHamilton-cycle 58Hamilton-Cycle

pTSP 663-SAT

psubset-sum 68subset-sum

pset-partition 743-SAT

p

k-colorability 7645

46x1x2x3f1=(x4

x3)1342x4x5x6x7f2=(x5

x1

x2)f3=(x6

x1

x2

x4)f4=(x7

x5

x6)

=x7

f1

f2

f3

f4

=x7

(x4

x3)(x5

x1

x2)(x6

x1

x2

x4)(x7

x5

x6)例因为为逻辑门i而构造的表达式fi正确地定义了其输出和输入变量之间的关系，所以容易看出电路C可被满足当且仅当

可被满足。另外，构造表达式

的时间显然是门的个数和连线个数的多项式函数，所以有Circuit-SAT

p

SAT。472. SAT问题

p

3-SAT问题3-SAT是SAT的一个子问题，因为表达式

必须是一个3-CNF。CNF(conjunctiveformalform)称为合取范式，它由一系列子句(Clause)用与(AND)运算连结而成，而每个子句由若干个文字用或(OR)运算连结而成。一个文字(literal)是指一个布尔变量或者变量的非。如果每个子句正好有3个文字，则表达式

称为3-CNF。例如:

=(x1

x1

x2)

(x3

x2

x4)

(

x1

x3

x4)。3-SAT问题是判断一个给定的3-CNF的表达式

是否可满足。下面，我们说明如何把SAT问题的一个实例多项式转换为一个

3-SAT的实例。我们用下面的例子來解释。假设SAT问题的一个实例是：

=((x1

x2)

((

x1

x3)

x4))

(

x2

x3)多项式转换算法如下：(接下页)48多项式转换算法(继续1)如下图(14-10)所示，

可以用一个二叉树来表示，用一个新变量代表每个内结点运算后的输出变量。这一步可在多项式时间内完成。

=((x1

x2)

((

x1

x3)

x4))

(

x2

x3)。

x2x3

x1x3x4x1x2y1y2y3y4y5y6

’=y1

(y1

(y2

y3))

(y2

(y4

y5)

(y3

(

x2

x3))

(y4

(x1

x2))

(y5

(y6

x4))

(y6

(

x1

x3))(2) 为每个内结点构造一个布尔表达式来表示它的输出变量和它的两个输入变量之间的关系。然后，把所有这些小表达式以及根结点的输出变量用与的运算串连起来得到表达式

’

(上图)。(接下页)49多项式转换算法(继续2)(3)

为

’中每个小表达式构造一真值表，然后找出一个3-CNF表达式来实现这个真值表。我们以本例中表达式y1

(y2

y3)为例说明。y1y2y3y1

(y2

y3)00010011010101101000101011001111由这个真值表，可得到一个等于0的析取范式(DNF):(

y1

y2

y3)

(y1

y2

y3)

(y1

y2

y3)

(y1

y2

y3)。(接下页)50多项式转换算法(继续3)析取范式(DNF)为：(

y1

y2

y3)

(y1

y2

y3)

(y1

y2

y3)

(y1

y2

y3)。再用德摩根(DeMorgan)定理把这个析取范式变为等于1的3-CNF:(y1

y2

y3)

(

y1

y2

y3)

(

y1

y2

y3)

(

y1

y2

y3)。因为真值表中等于0的行最多是8个，所以这个3-CNF中的子句最多有8个，因此在线性时间里可以完成对

’中所有小表达式的变换，即把所有小表达式变换为等价的3-CNF表达式。把

’中每个小表达式换为等价的3-CNF表达式后得到的表达式

’’就是我们从SAT问题一个实例构造得到的3-CNF表达式。显然，

’’的构造可在多项式时间内完成。又因为

’’可被满足当且仅当’可被满足，而

’可被满足当且仅当

可被满足。因此有SAT问题

p

3-SAT问题。513. 3-SAT问题

p

Clique问题图G的一个子图如果是个完全图，则称为一个团(clique)。给定图G，找它的一个最大的团是个优化型问题。对应的判断型问题是:给定图G和正整数k，G是否含有一个k-clique(由k个顶点形成的团)？注意，这里的k不是常数。否则，穷举搜索一个有常数k个顶点的团只需(nk)时间。下面解释，如何把3-SAT问题多项式归约到Clique问题。构造k-clique问题实例的多项式算法假设3-SAT的一个实例是：

=C1

C2…

Cm。子句Ci

(1

i

m)

中3个文字是li,1，li,2，li,3。构造对应的k-clique问题实例，图G(V,E)，的步骤如下：构造3m个顶点，分别对应3m个文字，即V={li,1，li,2，li,3|1

k

m}。每个子句对应的3个点为一小组，一共m组。(接下页)52构造k-clique问题实例的多项式算法(继续1)(2) 边的集合E的组成如下：同一组中3个点之间没有边，不同组的任何两点之间，只要不代表互补的两个文字，构造一条边。这里，互补是指一个变量和它的非。

下图(14-12)显示了一个从表达示转换为一个图的例子。C2=

x1

x2

x3C3=x1

x2

x3

x2x1C1=x1

x2

x3

x3

x1x2x3表达式：

=(x1

x2

x3)(

x1

x2

x3)(x1

x2

x3)x1

x2

x3构造的图接下页53构造k-clique问题实例的多项式算法(继续2)(3)

构造好图G以后，置k=m，则转換完成。上面转换显然可在多项式时间内完成。现在证明

可被满足当且仅当所构造的图有一个m-clique。假设

可被满足。我们从每个子句中选一个赋值为1的文字，一共m个文字。这m个文字对应的m个顶点一定形成一个m-clique。理由如下。因为这m个顶点对应的文字赋值为1，这m个文字中不可能有互补的两个文字。又因为它们分属m个不同的小组，所以任两个顶点间一定有边。所以这m个顶点形成一个m-clique。假设所构造图有一个m-clique。(接下页)54构造k-clique问题实例的多项式算法(继续3)假设所构造图有一个m-clique。那么，这m个顶点必定分属于m个不同的小组，它们对应的m个文字必分属于不同的子句。我们可将这m个文字赋以1。因为这m个文字中任意两个之间不可能互补，所以这样的赋值不会产生矛盾。然后把已赋值的文字的非赋值为0。这样一来，每个字句中至少有一文字被赋以1，所以表达式可被满足。对这k=m个所选文字以及它们的非赋值以后，也许还有没被赋值的变量，我们可将这样的变量及它的非分别赋以1和0。以上证明了表达式

可被满足当且仅当所构造图有一个k-clique。因此，3-SAT问题

p

Clique问题。55

56

(a){a,b,e,f}是图G的一个团acfdegb(b){c,d,g}是图G’的一个复盖acfdegb

57

585. vertex-Cover

p

Hamilton-Cycle假设vertex-cover的特例是图G和k，多项式转换算法构造图G’如下。第1步: 对应于G中每一条边(u,v)，构造一个小图Wuv，称为小器具。下图(14-14(a))显示了这个构造。uv,1uv,2vu,1vu,2(a)Wuv

的构造uv,1uv,2vu,1vu,2(b)

第1种一次穿越uv,1uv,2vu,1vu,2(c)

第2种一次穿越uv,1uv,2vu,1vu,2(d)

两次穿越Wuv含12个点。其中有标记的4个点与图中其他点相连。如果它被G’的一条哈密尔顿回路穿过的话，只能有三种可能。图中(b)(c)(d)显示了这三种可能的情况。59

uabc(a)

顶点u有3条边(b)

Du把与u关联的边所对应的小器具串连起来ua,1ua,2au,1au,2Wua

ub,1ub,2bu,1bu,2Wub

uc,1uc,2cu,1cu,2Wuc

60几点说明：Du提供了一条从(uv1,1)进，到(uvd,2)出的，穿过所有与u关联的边所对应的小器具的路径。在穿过每一个小器具时，可选择穿过所有12个点或只穿越6个点。我们用Pu表示这条路径。对G中一条边(u,v)来说，Wuv

与Wvu是同一个小器具，在G’中只出现一次。但对Du和Dv说，它们都要分别把Wuv

串连一次，不同的是，Dv连的口子是(vu,2)和(vu,1)，而Du连的口子是(uv,2)和(uv,1)。这也就是说，u和v各自用Wuv不同一侧的两个口子。路径Pu也许会在哈密尔顿回路中用到，也许不用。如果它是哈密尔顿回路中一部分，在它穿越每个小器具Wuv时，是经过12个点还是6个点要看是否有另外一条路径Pv穿过Wuv。下页图(14-16)显示了一个有4个顶点和4条边的图G，以及为它所构造的4个小器具和4条路径。对应顶点u的路径的两端用Pu和P’u标注。61uabc图Gua,1ua,2au,1au,2Wua

ub,1ub,2bu,1bu,2Wub

uc,1uc,2cu,1cu,2Wuc

ba,1ba,2ab,1ab,2Wba

Pu

P’u

Pa

P’aPb

P’b

Pc

P’c

图14-1662第3步，在G’中加入k个点，s1,s2,…,sk。然后将点si

(1

i

k)

与每一个Du

(u

G)的两头相连。下图(14-17)显示了，当k=2时，在图14-16基础上完成这一步之后的图。这一步之后，G’构造完成。aWua

Wub

Wuc

ubc图GWba

Pu

P’uPa

P’aPb

P’bPc

P’cs1s2与s1相同图14-1763

64Wua

Wub

Wuc

uabc图GWba

Pu

P’uPb

Pb’

s1s2对应于2-cover{u,b}的哈密尔顿回路假设G’中有一条哈密尔顿回路，从点s1开始。因为每个顶点正好出现一次，我们可假定顶点s1,s2,…,sk,

s1顺序在回路中出现。既使不按这个顺序，把它们交换为这个顺序后仍然是一条哈密尔顿回路。(接下页)转换算法的正确性证明(继续1)65转换算法的正确性证明(继续2)我们用<Pi,P’i>表示点si和s(i+1)modk

(1

i

k)之间的一段路径。由小器具的构造知，<Pi,P’i>必定是对应于G中某个点u的路径Pu。我们把点u选为G的一个复盖中的点。这样，我们可一共选出k个点，形成k个点的集合S。我们说，S是G的一个k-cover。这是因为G’中每个小器具都被回路中某个路径Pu穿过，那么这个小器具对应的G中的边一定关联于顶点u。所以G中的每条边一定关联于顶点S中某个点，S是G的一个k-cover。这样，我们就证明了，G有一个k-cover当且仅当G’有哈密尔顿回路。因为构造图G’只需多项式时间，所以有Vertex-Cover

pHamilton-Cycle。66Hamilton-cycle

pTSP给定一个加权的完全图G，TSP问题(货郎担问题)，是找出G中一条总权值最小的哈密尔顿回路，称为货郎担回路。判断型问题是，G中是否存在一条总权值不大于k的哈密尔顿回路？多项式转换算法假设Hamilton-Cycle问题的一个实例是图G(V,E)。转换算法构造一个TSP的实例，包括图G’(V’,E’)和实数k。第1步，G’

G，也就是复制一个G，V’

V,E’

E。第2步，赋以当前E’中的每条边(u,v)的权值为0，即w(u,v)

0。第3步，如果(u,v)

E’，u

v，则把(u,v)加到E’中，并赋以权值1，即w(u,v)

1。这样一来，G’(V’,E’)就是一个加权的完全图。第4步，置k=n。转换完成。(接下页)67多项式转换算法(继续)下图(14-19)给出了一个构造G’的例子。其中第3步中加的边用粗线标出。dabcedabce(a)Hamilton-Cycle问题中的图G(b)

TSP问题中的图G’0000000111显然，图G有一条哈密尔顿回路当且仅当G’中有一条总长为0的货郎担回路。所以有Hamilton-Cycle

pTSP。687. 3-SAT

pSubset-Sum假设S是有n个正整数的集合。Subset-Sum(子集和)问题是问：能否从S中找出一个子集A使得A中所有整数之和恰好等于一个给定的目标值t。多项式转换算法假设

是一个含有n个变量和m个子句的3-CNF。设这n个变量为x1，x2，…，xn,这m个子句为C1，C2，…，Cm。我们将构造集合S和目标值t。S

有2n+2m

个数，每个整数有n+m位。这n+m位，从最高位(最左一位)到最低位依次对应着x1，x2，…，xn和C1，C2，…，Cm。下面是构造的具体步骤。(接下页)69多项式转换算法(继续1)第1步，为每个变量xi

(1

i

n)构造两个整数，vi和v’i，分别对应xi和

xi。它们的值是这样决定的：在对应于xi

的那一位上，vi和v’i都是1，而对应于其他的xj

(j

i)的位上都是0。在对应于Ck

(1

k

m)的那一位上，如果xi

Ck，那么vi的值为1，否则为0。同样的，如果

xi

Ck，那么在对应于Ck的位上，v’i的值为1，否则为0。这一步一共为集合S

构造了2n个数。以

=(x1

x2

x3)

(

x1

x2

x3)

(x1

x2

x3)为例，下图(14-20)的上半部分显示了这些整数的构造。这个3-CNF有3个变量和3个子句，所以，这一部分一共构造了6个整数，每个整数都是6位数。70

x1x2x3C1C2C3v1=100101v’1=100010v2=010101v’2=010010v3=001001v’3=001110