《计算理论导引7时间复杂性》由会员分享，可在线阅读，更多相关《计算理论导引7时间复杂性（111页珍藏版）》请在金锄头文库上搜索。
1、引言qChurch-Turing论题论题：能够用总停机的：能够用总停机的Turing机计算的函数机计算的函数和识别的语言是可计算的（可判定的）；和识别的语言是可计算的（可判定的）；理论可计算理论可计算q计算复杂性理论计算复杂性理论研究计算模型在各种资源（主要是研究计算模型在各种资源（主要是时间时间、空间空间等）限制下的计算能力；等）限制下的计算能力；实际可计算实际可计算q一个可以计算的问题一个可以计算的问题需要多少时间和空间？需要多少时间和空间？q64层次梵塔，层次梵塔，1秒钟移动秒钟移动1000片（计算机作），要多少时间片（计算机作），要多少时间？q(264-1)/1000=5.846亿年亿
2、年1引言q复杂度和时间复杂度和时间：每秒作：每秒作106的基本运算需要的时间的基本运算需要的时间N=10N=20N=30N=40N=50N=60N10-5秒秒2*10-5秒秒3*10-5秒秒4*10-5秒秒5*10-5秒秒6*10-5秒秒N210-4秒秒4*10-4秒秒9*10-4秒秒16*10-525*10-436*10-4N310-3秒秒8*10-3秒秒27*10-4秒秒64*10-30.125秒秒0.216秒秒N510-1秒秒3.224秒秒1.7分分5.2分分13分分2N10-3秒秒117.9分分12.7天天35.7年年366世纪世纪3N0.059秒秒58分分6.5年年3855世世纪纪2
3、亿世纪亿世纪1.3*1013世纪世纪2引言Complexity：Hamilton回路问题（回路问题（HC）：任给一个无向图）：任给一个无向图G，问，问G中有中有Hamilton回路吗？回路吗？Hamilton回路是指经过每一个顶点且每一个顶点只经过一次的回路。回路是指经过每一个顶点且每一个顶点只经过一次的回路。q设设G有有n个顶点，由于回路没有始点和终点，可以任意定一个顶点作为排列的第个顶点，由于回路没有始点和终点，可以任意定一个顶点作为排列的第一个顶点，共有（一个顶点，共有（n-1）！个排列。当）！个排列。当n=25时，时，24！=6.2*1023.假设用一台超级假设用一台超级计算机计算，每
4、秒可以检查计算机计算，每秒可以检查1亿个排列。每年有亿个排列。每年有3.15*107秒，不停地工作，每年秒，不停地工作，每年可以检查可以检查3.15*1015个排列。检查完所有的排列需要个排列。检查完所有的排列需要1.97*108年，即年，即1亿亿9千千7百百年！年！q计算复杂性理论就是要研究计算模型在各种资源限制下的计算能力。将问题划计算复杂性理论就是要研究计算模型在各种资源限制下的计算能力。将问题划分成分成HardandEasy两大类。两大类。3引言co-TM recognizable（补集可识）TM-recognizable TM decidable PSPACE co-NPNP P4主
5、要内容主要内容7.1度量复杂性度量复杂性大大O 和小和小o 记法、分析算法、模型间的复杂性关系记法、分析算法、模型间的复杂性关系7.2P类类多项式时间、多项式时间、P 中的问题举例中的问题举例7.3NP类类NP中的问题举例、中的问题举例、P与与NP问题问题7.4NP完全性完全性多项式时间可归约性、多项式时间可归约性、NP完全性的定义、库克完全性的定义、库克-列文定理列文定理7.5几个几个NP完全问题完全问题顶点覆盖问题、哈密顿路径问题、子集和问题顶点覆盖问题、哈密顿路径问题、子集和问题5度量复杂性q考察下列例子：考察下列例子：语言语言A=0k1k |k0，显然，显然A是一个可判定的语言。是一个
6、可判定的语言。考察下面判定考察下面判定A的单带的单带TMM1M1=“对于输入串对于输入串w：1)扫描带子，如果在扫描带子，如果在1的右边发现的右边发现0，就，就拒绝拒绝。2)如果带上既有如果带上既有0也有也有1，就重复下一步。，就重复下一步。3)扫描带子，删除一个扫描带子，删除一个0和一个和一个1。4)如果所有如果所有1都被删除以后还有都被删除以后还有0，或者所有，或者所有0都被删除以后还有都被删除以后还有1，就，就拒绝拒绝。否则，如果在带上既没有剩下。否则，如果在带上既没有剩下0也没有剩下也没有剩下1，就，就接接受受。q考察判定考察判定A的图灵机的图灵机M1的算法所需的时间。的算法所需的时间
7、。6度量复杂性q把把算法的运行时间算法的运行时间纯粹作为表示纯粹作为表示输入字符串的长度输入字符串的长度来计算，来计算，而不考虑其它参数。而不考虑其它参数。q最坏情况分析（最坏情况分析（worst-caseanalysis）：考虑在某特定长度：考虑在某特定长度的所有输入上的最长运行时间。的所有输入上的最长运行时间。q平均情况分析（平均情况分析（average-caseanalysis）：考虑在某特定长：考虑在某特定长度的所有输入上的运行时间的平均值。度的所有输入上的运行时间的平均值。7度量复杂性定义定义定义定义7.17.1令令M 是一个在所有输入上都停机的确定型图灵机。是一个在所有输入上都停机
8、的确定型图灵机。M 的的运行时间运行时间或者或者时间复杂度时间复杂度，是一个函数，是一个函数f :NN，其中，其中N 是非负整数集合，是非负整数集合，f(n)是是M 在所在所有长度为有长度为n 的输入上运行时所经过的最大步数的输入上运行时所经过的最大步数。若若f(n)是是M 的运行时间，则称的运行时间，则称M 在时间在时间f(n)内运内运行，行，M 是时间图灵机。是时间图灵机。通常使用通常使用n 表示输入的长度。表示输入的长度。8渐进分析q因为算法的精确运行时间通常是一个复杂的表达式，所以因为算法的精确运行时间通常是一个复杂的表达式，所以一般是估计它的趋势和级别。一般是估计它的趋势和级别。q通
9、过一种称为通过一种称为渐进分析渐进分析(asymptoticanalysis)的方便的估的方便的估计形式，可以试图了解算法在长输入上的运行时间。计形式，可以试图了解算法在长输入上的运行时间。q只考虑算法运行时间的表达式的最高项，而忽略该项的系只考虑算法运行时间的表达式的最高项，而忽略该项的系数和其它低次项，因为在在长输入上，数和其它低次项，因为在在长输入上，最高次项最高次项的影响相的影响相比其它项比其它项占据主导地位占据主导地位。q例如，函数例如，函数f (n)=6n3+2n2+20n+45称称f 渐进地不大于渐进地不大于n3，表达这种关系的，表达这种关系的渐进记法渐进记法或大或大O 记记法法
10、是是f (n)=O(n3)。9大 O 和小 o记法定义定义定义定义7.27.2设设f 和和g是两个函数是两个函数f ，g：N R+。称。称f(n)=O(g(n)，若存在正整数，若存在正整数c 和和n0，使得对所有，使得对所有nn0有有f(n) cg(n)当当f(n)=O(g(n)时，称时，称g(n)是是f(n)的的上界上界，或更准，或更准确地说，确地说，g(n)是是f(n)的渐近上界，的渐近上界，以强调没有考虑常以强调没有考虑常数因子。数因子。10大 O 和小 o 记法例例7.3f1(n)是函数是函数5n3+2n2+22n+6。保留最高次项。保留最高次项5n3，并且，并且舍去它的系数舍去它的系
11、数5，得到，得到f1=O(n3)。验证该结果是否满足上面的形式定义。验证该结果是否满足上面的形式定义。令令c=6，n0=10，则对于，则对于所有所有n10，有，有5n3+2n2+22n+66n3。此外，有此外，有f1=O(n4)，因为，因为n4比比n3大，它也是大，它也是f1的一个渐近的一个渐近上界。上界。但是但是f1不等于不等于O(n2)，不论给，不论给c 和和n0赋什么值，始终不满足赋什么值，始终不满足定义的要求。定义的要求。11大 O 和小 o 记法例例7.4大大O记法以一种特别的方式与对数相互记法以一种特别的方式与对数相互影响。影响。通常通常写对数时必须写对数时必须指明基数指明基数(或
12、称为对数的底或称为对数的底)，如，如x=log2n。这里基数这里基数2表明表明该等式等价该等式等价于等式于等式2x=n。logbn 的的值值随着基数随着基数b 的的改变而乘以相应的常数倍，因为改变而乘以相应的常数倍，因为有恒等式有恒等式logbn =log2n / log2b。所以，写。所以，写f(n)=O(logn)时时不必再指明基数，因为不必再指明基数，因为最终最终要忽略常数因子。要忽略常数因子。12大 O 和小 o 记法q令令f2(n)是函数是函数3nlog2n+5nlog2log2n+2。此时此时f2(n) =O(nlogn)，因为，因为 logn 比比loglogn更占支配位置。更占
13、支配位置。qf(n) =O(n2)+O(n)等价于等价于f(n) =O(n2)q当当O 出现在指数位置，如出现在指数位置，如f(n) =2O(n)，代表着，代表着2cn 的一个上界。的一个上界。qf(n) =2O(logn)，代表，代表nc。（由。（由n =2logn 得得nc =2c log2n）q2O(1)代表了同样的界，因为表达式代表了同样的界，因为表达式O(1)代表不超过某个固代表不超过某个固定常数的上界。定常数的上界。13大O 和小o 记法q我们经常导出我们经常导出nc 的界，的界，c 是大于是大于0的常数。这种界称为的常数。这种界称为多多项式界项式界(polynamialbound
14、)。形如。形如的界，当的界，当 是大于是大于0的实数时，称为的实数时，称为指数界指数界(exponentialbound)。q大大O 记法记法指一个函数渐近地指一个函数渐近地不大于不大于另一个函数。另一个函数。q小小o 记法记法是渐进的是渐进的小于小于另一个函数。另一个函数。q大大O记法与小记法与小o记法的区别类似于记法的区别类似于和之间的区别。和之间的区别。14大O 和小o 记法定义定义定义定义7.57.5设设f 和和g 是两个函数是两个函数f ,g :N R+，如果，如果则称则称f(n)=o(g(n)。换言之，。换言之，f(n)=o(g(n)意味意味着对于任何实数着对于任何实数c0，存在一
15、个数，存在一个数n0，使得对所，使得对所有有nn0，f(n)cg(n)。15大O 和小o 记法例例7.6容易验证下面的等式。容易验证下面的等式。1)2)n =o(nlog(logn)3)nlog(logn)=o(nlogn)4)nlogn =o(n2)5)n2=o(n3)但是，但是，f(n)不会等于不会等于o(f(n)。16分析算法分析语言分析语言A =0k1k |k0对应的图灵机算法。对应的图灵机算法。M1=“对于输入串对于输入串w：1)扫描带子，如果在扫描带子，如果在1的右边发现的右边发现0，就，就拒绝拒绝。2)如果带上既有如果带上既有0也有也有1，就重复下一步。，就重复下一步。3)扫描带
16、子，删除一个扫描带子，删除一个0和一个和一个1。4)如果所有如果所有1都被删除以后还有都被删除以后还有0，或者所有，或者所有0都被删除以后还有都被删除以后还有1，就就拒绝拒绝。否则，如果在带上既没有剩下。否则，如果在带上既没有剩下0也没有剩下也没有剩下1，就，就接受接受。q步骤步骤1中，机器扫描带以验证输入的形式是中，机器扫描带以验证输入的形式是0*1*。执行这次扫描需要。执行这次扫描需要n步步。读写头重新放置在带的左端另外需要读写头重新放置在带的左端另外需要n步步。共需要。共需要2n步步。即。即O(n)步。步。q在步骤在步骤2和和3中，机器反复扫描带，在每一次扫描中删除一个中，机器反复扫描带
17、，在每一次扫描中删除一个0和一个和一个1。每每一次扫描需要一次扫描需要O(n)步步。因为每一次扫描删除两个符号，所以。因为每一次扫描删除两个符号，所以最多扫描最多扫描n/2次次。于是步骤。于是步骤2和和3需要的全部时间是需要的全部时间是(n/2)O(n)=O(n2)步。步。q在步骤在步骤4中，机器扫描一次来决定是接受还是拒绝。最多需要中，机器扫描一次来决定是接受还是拒绝。最多需要O(n)步。步。q所以，所以，M1在长度为在长度为n的输入上总共耗时为的输入上总共耗时为O(n)+O(n2)+O(n)，或，或O(n2)。换。换言之，它的言之，它的运行时间是运行时间是O(n2)。17时间复杂性类定义定
18、义定义定义7.77.7令令t :N R+是一个函数。定义是一个函数。定义时间复杂性类时间复杂性类TIME(t(n)为由为由O(t(n)时间的图灵机判定的时间的图灵机判定的所有所有语言的集合语言的集合。语言语言A =0k1k |k0，ATIME(n2)，因为因为M1在时间在时间O(n2)内判定内判定A，而，而TIME(n2)包括所有在时包括所有在时间内可判定的语言。间内可判定的语言。是否存在渐近更快地判定是否存在渐近更快地判定A的机器呢？的机器呢？在每次扫描中删除两个在每次扫描中删除两个0和两个和两个1，如何？，如何？18分析 M2 的时间复杂性q下面机器下面机器M2采用不同的方法，可以更快地判
19、定采用不同的方法，可以更快地判定A。ATIME(nlogn)。M2=“对输入串对输入串w：1)扫描带，如果扫描带，如果1的右边发现的右边发现0，就，就拒绝拒绝。2)只要在带上还有只要在带上还有0和和1，就重复下面的步骤。，就重复下面的步骤。3)扫描带，检查剩余的扫描带，检查剩余的0和和1的总数是偶数还是奇数。的总数是偶数还是奇数。若是奇数，就若是奇数，就拒绝拒绝。4)再次扫描带，从第一个再次扫描带，从第一个0开始，开始，隔一个删除一个隔一个删除一个0；然后从第一个然后从第一个1开始，开始，隔一个删除一个隔一个删除一个1.5)如果带上不再有如果带上不再有0和和1，就，就接受接受。否则。否则拒绝拒
20、绝。”q首先注意，每一步都消耗首先注意，每一步都消耗O(n)的时间。的时间。q步骤步骤1和和5执行一次，共需要执行一次，共需要O(n)时间。时间。q步骤步骤4在每一次执行时至少删除一半的在每一次执行时至少删除一半的0和和1，所以至多，所以至多1+log2n次循环就可次循环就可以把全部字符删除。于是，步骤以把全部字符删除。于是，步骤2、3和和4总共消耗时间总共消耗时间(1+log2n)O(n)，即，即O(nlogn)。M2的运行时间是的运行时间是O(n)+O(nlogn)=O(nlogn)。qATIME(nlogn)。这个结果在单带图灵机上不可能进一步改进。这个结果在单带图灵机上不可能进一步改进
21、。q单带图灵机在单带图灵机在o(nlogn)时间内判定的语言都是正则语言时间内判定的语言都是正则语言。19分析M3的时间复杂性q如果图灵机有第二条带，就可以在如果图灵机有第二条带，就可以在O(n)时间（也称为线性时间）内判定语时间（也称为线性时间）内判定语言言A。下面的两带图灵机。下面的两带图灵机TMM3在线性时间内判定在线性时间内判定A。M3=“对于输入串对于输入串w：1)扫描带，如果扫描带，如果1的右边发现的右边发现0，就，就拒绝拒绝。2)扫描带扫描带1上的上的0，直到第一个，直到第一个1时停止，同时把时停止，同时把0复制到带复制到带2上。上。3)扫描带扫描带1上的上的1直到输入的末尾。每
22、次从带直到输入的末尾。每次从带1上读到一个上读到一个1，就在带，就在带2上删除一个上删除一个0，如果在读完，如果在读完1之前所有的之前所有的0都被删除，就都被删除，就拒绝拒绝。4)如果所有如果所有0都被删除，就都被删除，就接受接受。如果还有。如果还有0剩下，就剩下，就拒绝拒绝。”q四个步骤中每一步需要四个步骤中每一步需要O(n)步，所以全部的运行时间是步，所以全部的运行时间是O(n)，因而是线，因而是线性的。性的。q注意，这可能是最好的运行时间，因为光是读输入就需要注意，这可能是最好的运行时间，因为光是读输入就需要n步。步。20A 的 C 程序A = 0k1k | k=0,1,2, . 先用用
23、C语言写程序判断串 s 是否 0k1k Bool M(char *s) int L=strlen(s) /扫描一遍 O(n) if (L%2)!=0 return false; /长度不是偶数 else N=L/2; for( k=1;kN; k+) / if (sk !=0) return false; /O(n) if (sk+N!=1) return false; /相当于第二条带 O(n) return true; 判断一个串，用 O(n)时间. 使用的资源:随机存取,数组，两带图灵机，21总结 A 的运行时间q给出一个单带给出一个单带TMM1，能够在时间，能够在时间O(n2)内判定内
24、判定A，以及一，以及一个更快的单带个更快的单带TMM2，能够在时间，能够在时间O(nlogn)内判定内判定A。两。两带带TMM3能在能在O(n)时间内判定语言时间内判定语言A。q因此因此A在单带在单带TM上的时间复杂度是上的时间复杂度是O(nlogn)，在两带，在两带TM上是上是O(n)。q注意注意A的复杂度与选择的计算模型有关。的复杂度与选择的计算模型有关。22复杂性理论与可计算性理论的区别q在在可计算性理论可计算性理论中，丘奇中，丘奇-图灵论题断言，图灵论题断言，所有合理的计算所有合理的计算模型都是等价的模型都是等价的，即它们所判定的语言类都是相同的。，即它们所判定的语言类都是相同的。q在
25、在复杂性理论复杂性理论中，中，模型的选择影响语言的时间复杂度模型的选择影响语言的时间复杂度。如。如在一个模型上线性时间内可判定的语言，在另一个模型上在一个模型上线性时间内可判定的语言，在另一个模型上就不一定是线性时间内可判定的。就不一定是线性时间内可判定的。q在复杂性理论中，在复杂性理论中，根据计算问题的时间复杂度来对问题分根据计算问题的时间复杂度来对问题分类类。23模型间的复杂性关系定理定理定理定理7.87.8设设t(n)是一个函数，是一个函数，t(n)n。则每一个时间。则每一个时间t(n)的的多带多带图灵机都和某一个图灵机都和某一个O(t2(n)时间的时间的单带单带图灵图灵机等价。机等价。
26、S 用它的一条带表示用它的一条带表示M 的所有的所有k条带条带的内容。这些带连续存放，的内容。这些带连续存放，M 的读的读写头的位置都标在恰当的方格上。写头的位置都标在恰当的方格上。01010Maaaba#01010#aaa#ba#S24模型间的复杂性关系01010Maaaba#01010#aaa#ba#S开始时，开始时，S 让它的带形成表示让它的带形成表示M 的所有带的格式，然后模拟的所有带的格式，然后模拟M 的步骤。的步骤。为了模拟为了模拟M 的一步，的一步，S 扫描带上的所有信息，扫描带上的所有信息，确定在确定在M 的读写头下的符的读写头下的符号号。然后。然后S 再次扫描带，再次扫描带，
27、更新带内容和读写头位置更新带内容和读写头位置。如果。如果M 的读写头向右的读写头向右移动到带上以前没有读到的位置，那么移动到带上以前没有读到的位置，那么S 必须增加分配给这条带的存储空必须增加分配给这条带的存储空间。为此，它把自己的带的一部分向右移动一格。间。为此，它把自己的带的一部分向右移动一格。25模型间的复杂性关系01010Maaaba#01010#aaa#ba#S模拟模拟M 的每一步，的每一步，S执行两次扫描，执行两次扫描，还可能最多向右移动还可能最多向右移动k次。次。每一次用时每一次用时O(t(n) ，所以，模拟，所以，模拟M 的一步操作，的一步操作，S总共耗时总共耗时O(t(n)
28、。现在，来界定模拟所需要的全部时间。在开始阶段，现在，来界定模拟所需要的全部时间。在开始阶段，S让它的带形成恰当的让它的带形成恰当的格式格式，这需要这需要 O(t(n)步。随后，步。随后，S模拟模拟M 的的t(n)步操作，每模拟一步需要步操作，每模拟一步需要O(t(n)步，所以模拟部分需要步，所以模拟部分需要t(n)O(t(n)=O(t2(n)步。因此，整个的模步。因此，整个的模拟过程需要拟过程需要O(n)+O(t2(n)步。步。假定假定t(n)n（这是合理的假定，因为如果时间更少，（这是合理的假定，因为如果时间更少，M连输入都读不完），连输入都读不完），则则S的运行时间是的运行时间是O(t2
29、(n)，证毕。，证毕。26模型间的复杂性关系定义定义定义定义7.97.9设设N 是一个非确定型图灵机，并且是一个判定机。是一个非确定型图灵机，并且是一个判定机。N 的运行时间是函数的运行时间是函数f :NN ，其中其中 f(n)是在任何是在任何长度为长度为n 的输入上所有的计算分支中最大步数的输入上所有的计算分支中最大步数。27模型间的复杂性关系定理定理定理定理7.107.10设设t(n)是一个函数，是一个函数，t(n)n 。则每一个。则每一个t(n)时间时间的的非确定型单带图灵机非确定型单带图灵机都与某一都与某一2O(t(n)时间时间的确定的确定型图灵机型图灵机等价。等价。设设N是一个在时间
30、是一个在时间t(n)内运行的非确定型内运行的非确定型TM，构造确定型，构造确定型TMD，D通过搜索通过搜索N 的非确定型计算树来模拟的非确定型计算树来模拟N。在长度为在长度为n的输入上，的输入上，N的非确定型计算树的非确定型计算树的的每一个分支的长度最多是每一个分支的长度最多是t(n)，树的，树的每一个结点最多有每一个结点最多有b个子女个子女，其中，其中b是是N 的转移函数所决定的合法选择的最大值。因此的转移函数所决定的合法选择的最大值。因此树叶的总数最多是树叶的总数最多是bt(n)。0010Dxx#01x12332312113输入带模拟带地址带28模型间的复杂性关系模拟过程以宽度优先法探查这
31、棵树。换句话说，在访问深度为模拟过程以宽度优先法探查这棵树。换句话说，在访问深度为d+1的结点之前，的结点之前，先访问所有深度为先访问所有深度为d 的结点。的结点。树中结点的总数小于最大叶数的两倍，因此用树中结点的总数小于最大叶数的两倍，因此用O(bt(n)作它的上界。作它的上界。从根出发下行到一个结点的时间是从根出发下行到一个结点的时间是O(t(n)。因此，因此，D的运行时间是的运行时间是O(t(n)bt(n)=2O(t(n)。TMD有三条带。把它转变为单带有三条带。把它转变为单带TM，最多使运行时间乘方。这样，单带模，最多使运行时间乘方。这样，单带模拟机的运行时间是拟机的运行时间是(2O(
32、t(n)2=2O(2t(n)=2O(t(n)，定理得证。，定理得证。 0010Dxx#01x12332312113输入带模拟带地址带29主要内容主要内容7.1度量复杂性度量复杂性大大O 和小和小o 记法、分析算法、模型间的复杂性关系记法、分析算法、模型间的复杂性关系7.2P类类多项式时间、多项式时间、P 中的问题举例中的问题举例7.3NP类类NP中的问题举例、中的问题举例、P与与NP问题问题7.4NP完全性完全性多项式时间可归约性、多项式时间可归约性、NP完全性的定义、库克完全性的定义、库克-列文定理列文定理7.5几个几个NP完全问题完全问题顶点覆盖问题、哈密顿路径问题、子集和问题顶点覆盖问题
33、、哈密顿路径问题、子集和问题30多项式时间q定理定理7.8和定理和定理7.10显示出一个重要的差别。一方面，问题的时间复杂性显示出一个重要的差别。一方面，问题的时间复杂性在在确定型单带和多带图灵机确定型单带和多带图灵机上最多是平方或上最多是平方或多项式多项式的差异；另一方面，的差异；另一方面，在在确定型和非确定型图灵机确定型和非确定型图灵机上，问题的时间复杂性最多是上，问题的时间复杂性最多是指数指数差异。差异。q典型的指数时间算法来源于通过搜索解空间来求解问题，这称为典型的指数时间算法来源于通过搜索解空间来求解问题，这称为蛮力搜蛮力搜索（索（brute-forcesearch）。例如，分解一个
34、数为素数因子的一种方法是。例如，分解一个数为素数因子的一种方法是搜遍所有可能的因子。搜索空间的规模是指数的，所以这种搜索需要指搜遍所有可能的因子。搜索空间的规模是指数的，所以这种搜索需要指数时间。有时候，通过更深入地理解问题，可以避免蛮力搜索，从而可数时间。有时候，通过更深入地理解问题，可以避免蛮力搜索，从而可能会找到更实用的多项式时间算法。能会找到更实用的多项式时间算法。q所有合理的确定型计算模型都是所有合理的确定型计算模型都是多项式等价的（多项式等价的（polynomiallyequivalent），也就是说，它们中任何一个模型都可以模拟另一个，而运，也就是说，它们中任何一个模型都可以模拟
35、另一个，而运行时间只增长多项式倍。行时间只增长多项式倍。当称所有合理的确定型模型都多项式等价时当称所有合理的确定型模型都多项式等价时，它足够广泛，它足够广泛，能容纳那些和实际计算机运行时间近似的模型能容纳那些和实际计算机运行时间近似的模型。例如，定。例如，定理理7.8表明确定型单带和多带固灵机模型是多项式等价的。表明确定型单带和多带固灵机模型是多项式等价的。31多项式时间在理论中，在理论中，P类扮演核心的角色，它的重要性在于：类扮演核心的角色，它的重要性在于：1)对于所有与确定型单带图灵机多项式等价的计算模型来说，对于所有与确定型单带图灵机多项式等价的计算模型来说，P是不变的。是不变的。2)P
36、大致对应于在计算机上实际可解的那一类问题。大致对应于在计算机上实际可解的那一类问题。第第1条表明，在数学上，条表明，在数学上，P是一个稳健的类，它不受所采用的具体计算模型是一个稳健的类，它不受所采用的具体计算模型的影响。的影响。第第2条表明，从实用的观点看，条表明，从实用的观点看，P是恰当的。当一个问题在是恰当的。当一个问题在P中的时候，就有中的时候，就有办法在时间办法在时间nk(k是常数是常数)内求解它。至于这么长时间是否实用就依赖于内求解它。至于这么长时间是否实用就依赖于k和和实际的应用情况。实际的应用情况。定义定义定义定义7.117.11P是是确定型单带图灵机确定型单带图灵机在在多项式时
37、间内可判定多项式时间内可判定的语言的语言类。换言之，类。换言之，PTIME(nk)32P中的问题举例q当给出多项式时间算法时，给出的是算法的高层描述，没有当给出多项式时间算法时，给出的是算法的高层描述，没有提及计算模型的特点，这样做回避了带和读写头运动的繁琐提及计算模型的特点，这样做回避了带和读写头运动的繁琐细节。细节。q分析一个算法，证明它在多项式时间内运行，需要两步：分析一个算法，证明它在多项式时间内运行，需要两步：1)必须为算法在长为必须为算法在长为n 的输入上运行时所需要的步骤给出多的输入上运行时所需要的步骤给出多项式上界（一般用大项式上界（一般用大O 记法）。记法）。2)必须考虑算法
38、描述中的每一步，保证它们都可以由合理的必须考虑算法描述中的每一步，保证它们都可以由合理的确定型模型在多项式时间内实现。确定型模型在多项式时间内实现。q需要注意的问题所用的编码方法。合理的方法就是允许在多需要注意的问题所用的编码方法。合理的方法就是允许在多项式时间内把对象编码项式时间内把对象编码/解码为自然的内部表示或其它合理的解码为自然的内部表示或其它合理的编码。编码。q图的一种合理编码是它的结点和边的序列。另一种是相邻矩图的一种合理编码是它的结点和边的序列。另一种是相邻矩阵，其中若从结点阵，其中若从结点i 到结点到结点j有边，则第有边，则第(i ,j )项为项为1，否，否则为则为0。33P中
39、的问题举例-PATH有向图有向图G 包含结点包含结点s 和和t ，如图所示。，如图所示。PATH问题问题就是要就是要确定是否存在从确定是否存在从s 到到t 的有向路径的有向路径。PATH=|G 是具有从是具有从s 到到t 的有向路径的有向图的有向路径的有向图st34P中的问题举例-PATH定理定理定理定理7.127.12PATHP 证明思路：证明思路： 通过给出判定通过给出判定PATH的多项式时间算法来证明该定理。的多项式时间算法来证明该定理。PATH 的蛮力算法的蛮力算法通过通过考察考察G 中所有可能路径来确定是否存在从中所有可能路径来确定是否存在从s 到到t 的的有向路径有向路径。一条可能
40、路径就是一条可能路径就是G 中长度最多为中长度最多为m 的结点序列，的结点序列，m 是是G 中的节点数。中的节点数。但是这些可能的路径数是但是这些可能的路径数是mm，这是，这是G 中结点数的指数倍。因此该蛮力算中结点数的指数倍。因此该蛮力算法消耗指数时间。法消耗指数时间。为了获得为了获得PATH 的多项式时间算法，必须设法避免蛮力搜索。一种方法是的多项式时间算法，必须设法避免蛮力搜索。一种方法是采用图搜索方法，如宽度优先搜索。连续标记采用图搜索方法，如宽度优先搜索。连续标记G 中从中从s 出发，长度为出发，长度为1,2,3直到直到m 的有向路径可达的所有节点。的有向路径可达的所有节点。用多项式
41、可以容易地来界定该策略的运行时间。用多项式可以容易地来界定该策略的运行时间。35PATHPPATH 的一个多项式时间算法的一个多项式时间算法M 运行如下：运行如下：M“对输入对输入G, s, t，G是包含结点是包含结点s 和和t 的有向图：的有向图：1)在结点在结点s 上做标记。上做标记。2)复重下面步骤复重下面步骤3，直到不再有结点被标记。，直到不再有结点被标记。3)扫描扫描G 的所有边。如果找到一条边的所有边。如果找到一条边(a, b)，a 被标记，被标记，而而b 没有被标记，那么标记没有被标记，那么标记b。4)若若t 被标记，则被标记，则接受接受；否则，；否则，拒绝拒绝。”步骤步骤1和和
42、4只执行一次只执行一次。步骤步骤3最多执行最多执行m 次次，因为除最后一次外，每一，因为除最后一次外，每一次执行都要标记次执行都要标记G 中的一个未标记的结点。所以用到的总步数最多是中的一个未标记的结点。所以用到的总步数最多是1+1+m，是，是G 的规模的多项式。的规模的多项式。M 的步骤的步骤1和和4很容易用任问合理的确定型模型在多项式时间内实现。步很容易用任问合理的确定型模型在多项式时间内实现。步骤骤3需要扫描输入，检查某些结点是否被标记，这也容易在多项式时间内需要扫描输入，检查某些结点是否被标记，这也容易在多项式时间内实现。所以实现。所以M 是是PATH 的多项式时间算法。的多项式时间算
43、法。 36P中的问题举例- RELPRIMERELPRIME 代表检查两个数是否是互素问题。代表检查两个数是否是互素问题。RELPRIME =|x 与与y 互素互素定理定理定理定理7.137.13RELPRIMEP 解决该问题的一种算法是搜索这两个数的所有可能的公因子。如果没有发现解决该问题的一种算法是搜索这两个数的所有可能的公因子。如果没有发现大于大于1的公因子，就接受。然而，用二进制或其它任何以的公因子，就接受。然而，用二进制或其它任何以k 为基的记法为基的记法(k2)表示的数字的大小是它表示长度的指数倍。因此该蛮力算法需要搜表示的数字的大小是它表示长度的指数倍。因此该蛮力算法需要搜遍指数
44、多个可能的因子，消耗指数的运行时间。遍指数多个可能的因子，消耗指数的运行时间。改用一种古老的数值计算过程来求解该问题，称为改用一种古老的数值计算过程来求解该问题，称为欧几里德算法欧几里德算法(Euclideanalgorithm)，来计算最大公因子。两个自然数的，来计算最大公因子。两个自然数的最大公因子最大公因子(greatestcommondivisor)，即为，即为gcd(x,y)，能同时整除，能同时整除x 和和y 的最大整数。的最大整数。37RELPRIMEP证明证明:欧几里德算法欧几里德算法E 如下：如下：E=“对输入对输入，x 和和y 是二进制表示的自然数：是二进制表示的自然数：1)
45、重复下面的操作，直到重复下面的操作，直到y=0.2)赋值赋值x x mody3)交换交换x和和y4)输出输出x。”显然，若显然，若E 在多项式时间内运行且正确，则在多项式时间内运行且正确，则R 也在多项式时间内运行且正也在多项式时间内运行且正确。所以只需分析确。所以只需分析E 的时间和正确性。的时间和正确性。步骤步骤2的每一次执行的每一次执行(除了第一次有可能例外除了第一次有可能例外)，都把，都把x 的值至少减少一半。的值至少减少一半。每一次执行步骤每一次执行步骤3都使都使x 和和y 的值相互交换，所以每两次循环就使得的值相互交换，所以每两次循环就使得x 和和y原先的值至少减少一半。于是步骤原
46、先的值至少减少一半。于是步骤2和和3执行的最大次数是执行的最大次数是2log2x 和和2log2y 中较小的那一个。这两个对数与表示的长度成正比，步骤的执行次数是中较小的那一个。这两个对数与表示的长度成正比，步骤的执行次数是O(n)。E 的每一步仅消耗多项式时间，所以整个运行时间是多项式的。的每一步仅消耗多项式时间，所以整个运行时间是多项式的。算法算法R以以E为子程序求解为子程序求解RELPRIMER=“对输入对输入，x 和和y 是二进制表示的自然数：是二进制表示的自然数：1)在在上运行上运行E。2)若结果为若结果为1，就，就接受接受；否则；否则拒绝拒绝。”38P中的问题举例-上下文无关语言定
47、理定理定理定理7.147.14每一个上下文无关语言都是每一个上下文无关语言都是P的成员。的成员。证明思路：证明思路：定理定理4.8证明了每一个证明了每一个CFL是可判定的，并且为每一个是可判定的，并且为每一个CFL给出了判定算法。如果那个算法在多项式时间内运行，那么本定理作为推给出了判定算法。如果那个算法在多项式时间内运行，那么本定理作为推论就必然成立。回忆那个算法，看它运行得是否够快。论就必然成立。回忆那个算法，看它运行得是否够快。令令L是一个由是一个由CFGG 产生的产生的CFG，G 是乔姆斯基范式。由问题是乔姆斯基范式。由问题2.26知：因知：因G是乔姆斯基范式，是乔姆斯基范式，任何得到
48、字符串任何得到字符串w的推导都有的推导都有2n-1步步，n 是是w 的长度。当给的长度。当给L的判定机输入长为的判定机输入长为n的字符串时，它的字符串时，它通过试遍所有可能的通过试遍所有可能的2n-1步推导来判定步推导来判定L。如果其中有一个得到。如果其中有一个得到w 的推导，该判定机就接受；的推导，该判定机就接受；否则，就拒绝。否则，就拒绝。分析一下该算法可知，它不能在多项式时间内运行。分析一下该算法可知，它不能在多项式时间内运行。k 步推导的数量步推导的数量可能达到可能达到k 的指数，所以该算法可能需要指数时间。的指数，所以该算法可能需要指数时间。39P中的问题举例-上下文无关语言为了获得
49、多项式时间算法，在此介绍一种强有力的技术，称为为了获得多项式时间算法，在此介绍一种强有力的技术，称为动态规划动态规划。这种技术通过累积小的子问题的信息来解决大的问题。把子问题的解都记这种技术通过累积小的子问题的信息来解决大的问题。把子问题的解都记录下来，这样就只需对它求解一次。为此，把所有了问题编成一张表，当录下来，这样就只需对它求解一次。为此，把所有了问题编成一张表，当碰到它们时，把它们的解系统地填入表格。碰到它们时，把它们的解系统地填入表格。在本例中，考虑在本例中，考虑G 的每一个变元是否产生的每一个变元是否产生w 的每一个子串这样的子问题。的每一个子串这样的子问题。算法把子问题的解填入一
50、张算法把子问题的解填入一张nn表格。对于表格。对于ij，表的第，表的第(i,j)项包含产生项包含产生子串子串wiwi+1wj 的所有变元。的所有变元。ij 的表项没有使用。的表项没有使用。算法为算法为w 的每一子串填写表项。首先为长为的每一子串填写表项。首先为长为1的子串填写表项，然后是长的子串填写表项，然后是长为为2的子串，依此类推。它利用短子串的表顶内容来辅助确定长子串的表的子串，依此类推。它利用短子串的表顶内容来辅助确定长子串的表项内容。项内容。40P中的问题举例-上下文无关语言例如，假定该算法已经确定了由哪些变元产生所有长度不超过例如，假定该算法已经确定了由哪些变元产生所有长度不超过k
51、 的的子串。为了确定变元子串。为了确定变元A 是否产生某一长为是否产生某一长为k+1的子串，算法把该子串以的子串，算法把该子串以k种可能方式分裂为非空的两段。对于每一种分裂方式，算法考察每一条种可能方式分裂为非空的两段。对于每一种分裂方式，算法考察每一条规则规则ABC ，利用以前计算的表项来确定是否，利用以前计算的表项来确定是否B 产生第一段而且产生第一段而且C 产产生第二段。如果生第二段。如果B 和和C 都产生各自的段，那么都产生各自的段，那么A 就产生该子串，并且被就产生该子串，并且被加入相关联的表项。算法从长为加入相关联的表项。算法从长为1的串开始，对规则的串开始，对规则Ab 考察表格。
52、考察表格。41P中的问题举例-上下文无关语言证明：证明：令令G是产生是产生CFLL的乔姆斯基范式的的乔姆斯基范式的CFG，假设，假设S是起始变元。是起始变元。D=“对输入对输入w =w1wn:1）若）若w = 且且S 是一条规则，则是一条规则，则接受接受。处理处理w = 的情况的情况2）Fori =1to n：考察每一长为考察每一长为1的子串的子串3）对每一个变元对每一个变元A：4）检查检查Ab是否是一条规则，其中是否是一条规则，其中b =wi。5）若是，把若是，把A放入放入table（i，i）。）。6）Forl =2to nl是子串长度是子串长度7）ForI =1to n-l+1i是子串的起
53、始位置是子串的起始位置8）令令j =i +l-1j是子串的起始位置是子串的起始位置9）Fork =ito j-1k是分裂位置是分裂位置10）对每一条规则对每一条规则ABC：12）若若table（i，k）包含）包含B且且table（k+1，j）包含）包含C，则把，则把A 放入放入table（i，j）12）若）若S在在table（1，n）中，则）中，则接受接受；否则；否则拒绝拒绝。”42P中的问题举例-上下文无关语言现在分析现在分析D。每一步很容易在多项式时间内运行。步骤。每一步很容易在多项式时间内运行。步骤4和和5最多运行最多运行nv次，其中次，其中v是是G中的变元数，是与中的变元数，是与n无关
54、的固定常数；因此这两步运行无关的固定常数；因此这两步运行O(n)次。步骤次。步骤6最多运行最多运行n 次。步骤次。步骤6每运行一次，步骤每运行一次，步骤7最多运行最多运行n次。步次。步骤骤7每运行一次，步骤每运行一次，步骤8和和9最多运行最多运行n次。步骤次。步骤9每运行一次，步骤每运行一次，步骤10运行运行r 次，这里次，这里r是是G的规则数，是另一个固定常数。所以步骤的规则数，是另一个固定常数。所以步骤11，即该算法的内，即该算法的内层循环，运行层循环，运行O(n3)次。总计次。总计D执行执行O(n3)步。步。43主要内容主要内容7.1度量复杂性度量复杂性大大O 和小和小o 记法、分析算法
55、、模型间的复杂性关系记法、分析算法、模型间的复杂性关系7.2P类类多项式时间、多项式时间、P 中的问题举例中的问题举例7.3NP类类NP中的问题举例、中的问题举例、P与与NP问题问题7.4NP完全性完全性多项式时间可归约性、多项式时间可归约性、NP完全性的定义、库克完全性的定义、库克-列文定理列文定理7.5几个几个NP完全问题完全问题顶点覆盖问题、哈密顿路径问题、子集和问题顶点覆盖问题、哈密顿路径问题、子集和问题44NP 类q许多问题可以避免使用蛮力搜索而获得多项式时间解法。许多问题可以避免使用蛮力搜索而获得多项式时间解法。但是，在某些其它问题中，包括许多有趣而有用的问题，但是，在某些其它问题
56、中，包括许多有趣而有用的问题，避免蛮力搜索的努力还没有成功，求解它们的多项式时间避免蛮力搜索的努力还没有成功，求解它们的多项式时间算法还没有找到。算法还没有找到。q可能这些问题具有未知原理的多项式时间算法，但至今还可能这些问题具有未知原理的多项式时间算法，但至今还没有被发现，或者它们中的某些问题就是不能在多项式时没有被发现，或者它们中的某些问题就是不能在多项式时间内解决，它们可能是间内解决，它们可能是固有地难计算固有地难计算的。的。q一个不寻常的发现是，一个不寻常的发现是，许多问题的复杂性是联系在一起的许多问题的复杂性是联系在一起的。发现其中一个问题的多项式时间算法可以用来解决整个一发现其中一
57、个问题的多项式时间算法可以用来解决整个一类问题类问题。45多项式可验证性q许多事情许多事情,猜出困难，验证易。猜出困难，验证易。q例如，解方程例如，解方程x10+2x+7=1035q解方程难，解方程难，验算验算根根x=2容易容易。qHAMPATH =G,s,t|G是包含从是包含从s 到到t的哈密顿路径的有向图的哈密顿路径的有向图容易获得指数时间算法，但不知是否能在多项式时间内求解。容易获得指数时间算法，但不知是否能在多项式时间内求解。该问题有一个特点，称为该问题有一个特点，称为多项式可验证性多项式可验证性。虽然还不知道一种虽然还不知道一种快速（即多项式时间）快速（即多项式时间）的方法来确定图中
58、是否包含哈的方法来确定图中是否包含哈密顿路径，但是如果密顿路径，但是如果以某种方式（可能是指数时间算法）以某种方式（可能是指数时间算法）找到这样的路找到这样的路径，就可以相信它的存在。即：径，就可以相信它的存在。即：验证验证哈密顿路径的存在可能哈密顿路径的存在可能比确定比确定它的它的存在性存在性容易容易得多。得多。qCOMPOSITES =x |x =pq，整数，整数p,q1虽然不知道判断该问题的多项式时间算法，但是容易验证一个数是不是虽然不知道判断该问题的多项式时间算法，但是容易验证一个数是不是合数合数-只需要该数的一个因子即可。只需要该数的一个因子即可。46多项式可验证性定义定义定义定义7
59、.157.15语言语言A 的的验证机验证机(verifier)是一个算法是一个算法V，这里，这里Aw | 对某个字符串对某个字符串c，V 接受接受w,c因为只根据因为只根据w 的长度来度量验证机的时间，所以的长度来度量验证机的时间，所以多项式时间验证机多项式时间验证机在在w 的长度的多项式时间内运行。的长度的多项式时间内运行。若语言若语言A 有一个多项式时间验证机，则称它为有一个多项式时间验证机，则称它为多项式可验证的多项式可验证的。验证机利用额外的信息验证机利用额外的信息(在定义在定义7.15中用符号中用符号c 表示表示)来来验证字符串验证字符串w 是是A 的成员的成员。该信息称为。该信息称
60、为A 的成员资格的成员资格证书证书(certificate)，或，或证明证明(proof)。注意，对于多项式验证机，证书具有多项式的长度注意，对于多项式验证机，证书具有多项式的长度(w 的长度的长度)，因为这是，因为这是该验证机在它的时间界限内所能访问的全部信息长度。该验证机在它的时间界限内所能访问的全部信息长度。对于对于 HAMPATH 问题，字符串问题，字符串 HAMPATH 的证书就只是一条从的证书就只是一条从s 到到t的哈密顿路径。的哈密顿路径。对于对于COMPOSITE问题，合数问题，合数x的证书只是它的一个因子。的证书只是它的一个因子。47NP类定义定义定义定义7.167.16NP
61、是具有是具有多项式时间验证机多项式时间验证机的语言类。的语言类。NP即即非确定型多项式时间非确定型多项式时间（nondeterministicpolynomialtime）。）。在在NP中的问题有时被称为中的问题有时被称为NP问题。问题。48判定 HAMPATHq在非确定型多项式时间内判定在非确定型多项式时间内判定HAMPATH 问题的非确定型图灵机问题的非确定型图灵机(NTM)：N1=“对输入对输入，这里，这里G是包含结点是包含结点s 和和t的有向图的有向图1)写一列写一列m 个数个数p1, p2,pm ，m 是是G 的结点数。列中每一个的结点数。列中每一个数都是从数都是从1到到m 中非确定
62、地挑选。中非确定地挑选。2)在列中检查重复性，若发现重复，则拒绝。在列中检查重复性，若发现重复，则拒绝。3)检查检查s =p1和和t =pm是否都成立。若有一个不成立，则拒绝。是否都成立。若有一个不成立，则拒绝。4)对于对于1到到m-1中每一个中每一个i，检查，检查(pi，pi+1)是否是是否是G 的一条边。的一条边。若有一个不是，则拒绝。否则，所有检查都通过了，接受。若有一个不是，则拒绝。否则，所有检查都通过了，接受。”q算法分析算法分析在步骤在步骤1中，非确定性的选择显然在多项式时间内运行。中，非确定性的选择显然在多项式时间内运行。在步骤在步骤2和和3中，每一步是一次简单的检查，所以合起来
63、它们中，每一步是一次简单的检查，所以合起来它们仍在多项式时间内运行。仍在多项式时间内运行。步骤步骤4也显然在多项式时间内运行。也显然在多项式时间内运行。该算法在非确定型多项式时间内运行。该算法在非确定型多项式时间内运行。49NP类定理定理定理定理7.177.17一个语言在一个语言在NP中，当且仅当它能被某个非确定型中，当且仅当它能被某个非确定型多项式时间图灵机判定。多项式时间图灵机判定。一个多项式时间验证机和多项式时间一个多项式时间验证机和多项式时间NTM相互转换。相互转换。NTM通过猜想证书来模拟验证机通过猜想证书来模拟验证机，验证机通过把接受分支作为证书来模验证机通过把接受分支作为证书来模
64、拟拟NTM。50NP类从左向右的方向，设从左向右的方向，设ANP，要证，要证A 被多项式时间被多项式时间NTMN 判定。判定。由由NP的定义，存在的定义，存在A 的多项式时间验证机的多项式时间验证机V。假设假设V 是一个在时间是一个在时间nk 内运行的内运行的TM，构造，构造N 如下；如下；N“对长为对长为n 的输入的输入w。1)非确定地选择长为非确定地选择长为nk 的字符串的字符串c。2)在输入在输入上运行上运行V。3)若若V 接受，则接受；否则拒绝。接受，则接受；否则拒绝。”从右向左的方向，假设从右向左的方向，假设A 被多项式时间被多项式时间NTMN 判定，判定，构造多项式时间验证机构造多
65、项式时间验证机V 如下：如下：V “对输入对输入，这里，这里w,c 是字符串：是字符串：1)在输入在输入w 上模拟上模拟N，把把c 的每一个符号看作是对每一步的每一个符号看作是对每一步所做的非确定性选择的描述所做的非确定性选择的描述。2)若若N 的该计算分支接受，则接受；否则，拒绝。的该计算分支接受，则接受；否则，拒绝。” 51NP类定义定义定义定义7.187.18NTIME(t(n)=L | L是一个被是一个被O (t(n)时间的时间的非非确定型图灵机确定型图灵机判定的语言判定的语言推论推论推论推论7.197.19NP=kNTIME(nk)52NP中问题举例CLIQUE无向图中的无向图中的团
66、团(clique)是一个子图，其中是一个子图，其中每两个结点都有边每两个结点都有边相连相连。k团团就是包含就是包含k个的结点的团。个的结点的团。4-cliquegraph不是 5-cliqueCLIQUE =|G 是包含是包含k 团的无向图团的无向图53NP中问题举例CLIQUE定理定理定理定理7.207.20CLIQUE 属于属于NP。证明证明下面是下面是CLIQUE 的验证机的验证机V。V “对输入对输入,c：1)检查检查c 是否是是否是G 中中k 个结点的集合。个结点的集合。2)检查检查G 是否包含连接是否包含连接c 中结点的所有边。中结点的所有边。3)若两项检查都通过，则接受；否则，拒
67、绝。若两项检查都通过，则接受；否则，拒绝。”团即是证书团即是证书另一种证明另一种证明通过给出判定通过给出判定CLIQUE 的图灵机来证明。的图灵机来证明。N“对输入对输入，这里，这里G 是一个图：是一个图：1)非确定地选择非确定地选择G 中中k 个结点的子集个结点的子集c。2)检查检查G 是否包含连接是否包含连接c 中结点的所有边。中结点的所有边。3)若是，则接受；否则，拒绝。若是，则接受；否则，拒绝。”54NP中问题举例CLIQUE如果用确定图灵机来解决。如果用确定图灵机来解决。BoolDM()G中有中有m 个结点，其中有个结点，其中有k个个结点结点的子集有的子集有mk个，个，编码排序编码排
68、序1,2,.,mkfor(i=1;imk;i+)/按次序检查子集按次序检查子集cok=c中两两结点之间的边在中两两结点之间的边在G中；中；returnok;说明说明确定机用确定机用指数时间，可以解决。指数时间，可以解决。但不排除但不排除某个聪明人能找到某个聪明人能找到确定机确定机P时间的方法时间的方法55NP中问题举例SUBSET-SUMSUBSET-SUM =|s =x1,xk，且存在，且存在y1,yl x1,xk 使得使得 yi =t x1,xk和和y1,yl 被看做是被看做是多重集多重集，因此允许元素重复。，因此允许元素重复。 SUBSET-SUM 不属于不属于 SUBSET-SUM问题
69、的直观实例问题的直观实例(1)不找补不找补购物购物(2)装背包，又称背包问题装背包，又称背包问题56NP中问题举例SUBSET-SUM定理定理定理定理7.217.21SUBSET-SUM 属于属于NP。证明一证明一下面是下面是SUBSET-SUM 的验证机的验证机V。V “对输入对输入,c：1)检查检查c 是否是加起来等于是否是加起来等于 t 的数的集合。的数的集合。2)检查检查S 是否包含是否包含c 中的所有数。中的所有数。3)若两项检查都通过，则接受；否则，拒绝。若两项检查都通过，则接受；否则，拒绝。”证明二证明二通过给出判定通过给出判定SUBSET-SUM的非确定性多项式时间图灵机来证明
70、。的非确定性多项式时间图灵机来证明。N“对输入对输入：1)非确定地选择非确定地选择S 中的数的子集和中的数的子集和c。2)检查检查c 是否是加起来等于是否是加起来等于 t 的数的集合。的数的集合。3)若检查通过，则接受；否则，拒绝。若检查通过，则接受；否则，拒绝。”子集即是证书子集即是证书57关于 NP 中问题的说明q注意这些集合的补集，注意这些集合的补集，和和，不是很，不是很明显地属于明显地属于NP。q验证某种事物不存在好像要比验证它存在更加困难。验证某种事物不存在好像要比验证它存在更加困难。q我们定义了另外一个复杂性类，称为我们定义了另外一个复杂性类，称为coNP，它包括，它包括NP中中的
71、语言的补语言。还不知道的语言的补语言。还不知道coNP是否与是否与NP不同。不同。58P 与 NP 问题qP=成员资格可以快速地成员资格可以快速地判定判定的语言类的语言类qNP=成员资格可以快速地成员资格可以快速地验证验证的语言类的语言类NPPP=NP这两个可能中有一个是正确的这两个可能中有一个是正确的q求解求解NP语言的已知的最好方法语言的已知的最好方法确定性地使用指数时间确定性地使用指数时间。59NP完全性q在在P与与NP问题上的一个重大进展是在问题上的一个重大进展是在1970年代初出斯蒂年代初出斯蒂芬芬库克（库克（StephenCook）和列奥尼德）和列奥尼德列文（列文（LeonidLe
72、vin）完成的。）完成的。q他们发现他们发现NP中的某些问题的复杂性与整个类的复杂性相中的某些问题的复杂性与整个类的复杂性相关联关联。这些问题中任何一个如果存在多项式时间算法，那这些问题中任何一个如果存在多项式时间算法，那么所有么所有NP问题都是多项式时间可解的问题都是多项式时间可解的。这些问题称为。这些问题称为NP完全的完全的（NP-complete）。）。q在理论方面，试图证明在理论方面，试图证明P不等于不等于NP的研究者可以把注意的研究者可以把注意力集中到一个力集中到一个NP完全问题上。完全问题上。q在实践上，在实践上，NP完全性现象可以防止为某一具体问题浪费时完全性现象可以防止为某一具
73、体问题浪费时间，寻找本不存在的多项式时间算法。间，寻找本不存在的多项式时间算法。60NP完全性可满足性问题q布尔变量：取值为布尔变量：取值为TRUE和和FALSE，用，用1和和0表示。表示。q布尔运算：布尔运算：AND、OR和和NOT分别用分别用 、 、 表示。表示。q布尔公式：布尔公式： =( x y) (x y)。q公式的类型：重言式、矛盾式、可满足式公式的类型：重言式、矛盾式、可满足式q可满足性：对变量的某个可满足性：对变量的某个0,1赋值使得一个公式的值等于赋值使得一个公式的值等于1。SAT= |是可满足的布尔公式是可满足的布尔公式定理定理定理定理7.227.22库克库克-列文（列文（
74、Cook-Levin）定理）定理SATP，当且仅当，当且仅当P=NP。该定理把该定理把SAT 问题的复杂性和问题的复杂性和NP中所有问题的复杂性联系中所有问题的复杂性联系起来。起来。61多项式时间可归约性定义定义定义定义7.237.23若存在多项式时间图灵机若存在多项式时间图灵机M，使得在任何输入，使得在任何输入w上，上，M 停机时停机时f (w)恰好在带上，称函数恰好在带上，称函数f : * *为为多多项式时间可计算函数项式时间可计算函数。定义定义定义定义7.247.24语言语言A 称为称为多项式时间映射可归约多项式时间映射可归约到语言到语言B，或简，或简称称多项式时间可归约多项式时间可归约
75、到到B，记为，记为ApB，若存在多项，若存在多项式时间可计算函数式时间可计算函数f : * *，对于每一个，对于每一个w，有，有wA f(w)B，函数函数f 称为称为A 到到B 的的多项式时间多项式时间归约。归约。62多项式时间可归约性定理定理定理定理7.257.25若若ApB 且且BP，则，则A P。设设M是判定是判定B的多项式时间算法，的多项式时间算法，f 是从是从A到到B 的多项式时间归约。的多项式时间归约。判定判定A的多项式时间算法的多项式时间算法N的描述如下：的描述如下：N=“对于输入对于输入w ；1)计算计算f (w)。2)在输入在输入f (w)上运行上运行M，输出，输出M的输出。
76、的输出。”若若wA，则，则f(w)B，因为，因为f 是从是从A到到B的归约。的归约。于是，只要于是，只要wA，M 就接受就接受f (w)。另外，因为。另外，因为N 的两个步骤都是在多项式的两个步骤都是在多项式时间内运行，所以时间内运行，所以N 在多项式时间内运行。在多项式时间内运行。注意，步骤注意，步骤2在多项式时间内运行是因为两个多项式的合成还是多项式。在多项式时间内运行是因为两个多项式的合成还是多项式。633SATq3SAT是可满足性问题的一种特殊情况。是可满足性问题的一种特殊情况。q文字文字(literal)：一个布尔变量或布尔变量的非，如：一个布尔变量或布尔变量的非，如x或或 x。q子
77、句子句(clause)：是由：是由 连接起来的若干文字，如连接起来的若干文字，如(x y z)。q合取范式：由合取范式：由 连接的若干个子句，亦称为连接的若干个子句，亦称为cnf 。q3cnf：所有子句都有三个文字。：所有子句都有三个文字。3SAT= |是可满足的是可满足的3cnf 公式公式64多项式时间可归约性定理定理定理定理7.267.263SAT 多项式时间可归约到多项式时间可归约到CLIQUE 。证明思路：证明思路：给出从给出从3SAT 到到CLIQUE 的多项式时间归约的多项式时间归约f，它把公式转化，它把公式转化为图。为图。在构造的图中，指定大小的团对应于公式的满足赋值。图中的在构
78、造的图中，指定大小的团对应于公式的满足赋值。图中的结构被设计好用来模拟变量和子句的作用。结构被设计好用来模拟变量和子句的作用。65示例：从 3SAT 到 CLIQUEqFormula(4clauses,4variables):4变量变量的的3子句归约为团子句归约为团由由3合取范式造对应图的方法合取范式造对应图的方法设设有有k 个子句（这里个子句（这里k=4)(1)分分k组画组画3k个顶点，个顶点，(2)按子句中变量按子句中变量标记顶点，标记顶点，(3)连接不在同一组中的任意两连接不在同一组中的任意两顶点顶点(4)然后把矛盾的边去掉，然后把矛盾的边去掉，如如上述上述4步工作可在多项式时间内步工作
79、可在多项式时间内可完成即可完成即p时间映射归约时间映射归约66示例：从 3SAT 到 CLIQUE均均True, 是个满足的指是个满足的指派，对应顶点成为团派，对应顶点成为团 有有 4-clique均均True, 是个不是个不满足的指派满足的指派 非非 4-clique当公式为真时，每个当公式为真时，每个3-合取范式中至少一个变量为真，设红箭头所指为真合取范式中至少一个变量为真，设红箭头所指为真67多项式时间可归约性定理定理定理定理7.267.263SAT 多项式时间可归约到多项式时间可归约到CLIQUE 。证明：设证明：设是是k 个子句的公式，如个子句的公式，如 = (a1b1c1)(a2b
80、2c2)(akbkck)归约归约f 生成字符串生成字符串G，k，其中，其中G是如下定义的无向图。是如下定义的无向图。G中的结点分成中的结点分成k 组，每组三个结点，称为三元组组，每组三个结点，称为三元组t1，tk。每个三元组。每个三元组对应于对应于中的一个子句，三个元组中每个结点对应于相应子句的一个文字。中的一个子句，三个元组中每个结点对应于相应子句的一个文字。G的每个结点用它对应的的每个结点用它对应的中的文字做标记。中的文字做标记。除两种情形以外，除两种情形以外，G 的边连接了所有的节点对。同一个三元组内的节点无的边连接了所有的节点对。同一个三元组内的节点无边相连，相反标记的两个结点无边相连
81、，如边相连，相反标记的两个结点无边相连，如x2和和。现在说明这种构造为何能发挥作用，证明现在说明这种构造为何能发挥作用，证明是可满足的当且仅当是可满足的当且仅当G有有k团。团。68多项式时间可归约性假定假定有满足赋值。在满足赋值下，每个句子中至少一个文字为真。有满足赋值。在满足赋值下，每个句子中至少一个文字为真。在在G的的每个三元组中，选择在该满足赋值下为真的文字对应的结点。每个三元组中，选择在该满足赋值下为真的文字对应的结点。如果在某一如果在某一子句中不止一个文字为真，任意选择一个真文字即可。选择出来的结点将子句中不止一个文字为真，任意选择一个真文字即可。选择出来的结点将恰好形成一个恰好形成
82、一个k团：因为是从团：因为是从k 个三元组中的每一个中挑选一个结点，所个三元组中的每一个中挑选一个结点，所以选择的结点数为以选择的结点数为k。每一对选中的结点都有边相连，它们都不适合前面。每一对选中的结点都有边相连，它们都不适合前面描述的两种例外情形。它们不可能来自同一三元组，因为从每个三元组中描述的两种例外情形。它们不可能来自同一三元组，因为从每个三元组中只选一个结只选一个结点。它们也不可能有相反标记点。它们也不可能有相反标记，因为它们关联的文宇在该满足因为它们关联的文宇在该满足赋值下都为真。所以赋值下都为真。所以G 包含包含k 团。团。假定假定G 有有k 团团。因为在同一个三元组中的结点都
83、无边相连，所以因为在同一个三元组中的结点都无边相连，所以团中的任团中的任何两个结点都不在同一个三元组中何两个结点都不在同一个三元组中。因此。因此k 个三元组中的每一个都恰好包个三元组中的每一个都恰好包含团的一个含团的一个结点结点。给给的的变量变量赋真值，使得标记团结点的每个文字都为真赋真值，使得标记团结点的每个文字都为真。这可以办到，因为具有相反标记的两个这可以办到，因为具有相反标记的两个结结点点无边相连，所以不可无边相连，所以不可能能在两个在两个团中。给变量的这种赋值满足团中。给变量的这种赋值满足，因为每个三元组包含一个团因为每个三元组包含一个团结点，所以结点，所以每个子句包含一个赋值为每个
84、子句包含一个赋值为TRUE的文字。的文字。可满足可满足。69NP完全性定义从多项式时间可归约性的定义直接可得。从多项式时间可归约性的定义直接可得。定义定义定义定义7.277.27如果语言如果语言B 满足下面两个条件，就称为满足下面两个条件，就称为NP完全的完全的：1）B 属于属于NP，并且，并且2）NP中的每个中的每个A 都多项式时间可归约到都多项式时间可归约到B。定理定理定理定理7.287.28若上述的若上述的B 是是NP完全的，且完全的，且BP，则，则P=NP。70NP完全性定义已知已知C 属于属于NP，必须证明，必须证明NP中每一个中每一个A 都都多项式时间可多项式时间可归约到归约到C
85、。因为因为B 是是NP完全的，所以完全的，所以NP中的每个语言都多项式时间可中的每个语言都多项式时间可归约到归约到B，而，而B 又多项式时间可归约到又多项式时间可归约到C。多项式时间归约是可以复合的，即若多项式时间归约是可以复合的，即若A 多项式时间可归约多项式时间可归约C ，且且B 多项式时间可归约到多项式时间可归约到C，则，则A 多项式时间可归约到多项式时间可归约到C。因此。因此NP中的每个语言都多项式时间可归约到中的每个语言都多项式时间可归约到C。定理定理定理定理7.297.29若上述的若上述的B 是是NP完全的，且完全的，且B pC，C 属于属于NP，则则C 是是NP完全的。完全的。7
86、1库克-列文定理给给NP中的每一个语言中的每一个语言A构造一个到构造一个到SAT的多项式时间归约，的多项式时间归约，A的归约在的归约在字符串字符串w 上产生布尔公式上产生布尔公式，用它模拟，用它模拟A的的NP机器在输入机器在输入w上的运行。上的运行。首先证明首先证明SAT 属于属于NP。非确定型多项式时间机器可以猜测给定的公式。非确定型多项式时间机器可以猜测给定的公式的的一个赋值，当赋值满足一个赋值，当赋值满足时接受。时接受。下面，从下面，从NP中任取一个语言中任取一个语言A，证明，证明A 多项式可归约到多项式可归约到SAT。设设N 是在时间是在时间nk 内判定内判定A的非确定型图灵机，的非确
87、定型图灵机，k 是某个常数。是某个常数。（实际假定（实际假定N 在时间在时间nk-3）在在w 上，上，N 对应的画面是一张对应的画面是一张nk nk 的表格，其中行代表的表格，其中行代表N 在输入在输入w 上的上的一个计算分支的格局。一个计算分支的格局。定理定理定理定理7.307.30SAT 是是NP完全的。完全的。72库克-列文定理#q0w1w2wn#nknk起始格局起始格局第二个格局第二个格局第第nk个格局个格局窗口窗口73库克-列文定理q现在描述从现在描述从A 到到SAT 的多项式时间归约的多项式时间归约f 。在输入。在输入w上，该归约产生一个公式上，该归约产生一个公式。q从描述从描述
88、的变量开始，设的变量开始，设Q 和和 是是N 的状态集和带字母表，令的状态集和带字母表，令C=Q #。对于每个介于对于每个介于1到到nk 之间的之间的i和和j 以及以及C 中的每个中的每个s，有一个变量，有一个变量xi,j,s 。若。若xi,j, s 取值取值1，则意味着，则意味着celli,j包含包含s。q设计设计，使得变量的一个满足赋值确实对应，使得变量的一个满足赋值确实对应N 在在w 上的一个接受画面。公式上的一个接受画面。公式是四是四部分的部分的AND运算：运算：cell start move accept74库克-列文定理 start=accept=move保证，表的每一行都对应于上
89、一行的格局、按照保证，表的每一行都对应于上一行的格局、按照N 的规则、合法转的规则、合法转移得到的格局。它通过每一个移得到的格局。它通过每一个23窗口单元都是合法的来保证这一点。如窗口单元都是合法的来保证这一点。如果一个果一个23的窗口不违反由的窗口不违反由N的转移函数指定的动作，则称该窗口是的转移函数指定的动作，则称该窗口是合法合法的的。换言之，如果它可以出现在从一个格局正确地转移到另一个格局的过。换言之，如果它可以出现在从一个格局正确地转移到另一个格局的过程中，该窗口就称为合法的。程中，该窗口就称为合法的。75库克-列文定理q例，设例，设a, b, c是带字母表的成员，是带字母表的成员，q
90、1和和q2是是N 的状态的状态。假设在。假设在q1，读写头，读写头读取读取a 时，时，N 写一个写一个b ，仍在状态，仍在状态q1，并且右移。在状态，并且右移。在状态q1，读写头读取，读写头读取b 时，时，N 非确定地：非确定地：1)写一个写一个c，进入状态，进入状态q2并左移，或者并左移，或者2)写一个写一个a，进入状态，进入状态q2并右移。并右移。形式的表示为，形式的表示为， (q1,a)=(q1,b, R)， (q1,b)=(q2,c, L),(q2,a, R)。该机器的合法窗口的例子：。该机器的合法窗口的例子：aq1bq2ac#ba#baabaabq2bbbcbbaq1baaq2aaq
91、1aab76库克-列文定理该机器的不合法窗口：该机器的不合法窗口：abaaaabq1bq2bq2aq1bq1aa77库克-列文定理断言断言断言断言7.317.31如果表的顶行是起始格局，表中的每如果表的顶行是起始格局，表中的每一个窗口都是一个窗口都是合法的，那么表的每一合法的，那么表的每一行都是从上一行行都是从上一行合法转移得合法转移得到的格局。到的格局。q考虑表的任意两个相邻格局，称为上格局和下格局。考虑表的任意两个相邻格局，称为上格局和下格局。q在上格局中，每一个不与状态符号相邻的而且不含边界符号的单元，在上格局中，每一个不与状态符号相邻的而且不含边界符号的单元，都是某个窗口顶行的中间单元
92、且窗口顶行不含状态。因此该符号必定都是某个窗口顶行的中间单元且窗口顶行不含状态。因此该符号必定保持不变，出现在窗口的底行中间，即出现在底行格局的同一位置。保持不变，出现在窗口的底行中间，即出现在底行格局的同一位置。q窗口顶行的中间单元包含状态符号，这就使相应的三个位置按照转移窗口顶行的中间单元包含状态符号，这就使相应的三个位置按照转移函数的要求一致更新。因此，如果上格局是合法格局，那么下格局也函数的要求一致更新。因此，如果上格局是合法格局，那么下格局也是，并且下格局是根据是，并且下格局是根据N的规则从上格局转移得到。注意，这个证明的规则从上格局转移得到。注意，这个证明显然易懂，但它的关键依赖于
93、选择了大小为显然易懂，但它的关键依赖于选择了大小为23的窗口。的窗口。78库克-列文定理q考虑表的任意两个相邻格局，称为考虑表的任意两个相邻格局，称为上格局和下格局。上格局和下格局。断言断言断言断言7.317.31如果表的顶行是起始格局，表中的每如果表的顶行是起始格局，表中的每一个窗口都是一个窗口都是合法的，那么表的每一合法的，那么表的每一行都是从上一行行都是从上一行合法转移得合法转移得到的格局。到的格局。q分析归约的复杂性分析归约的复杂性q画面是画面是nknk 表格，包含表格，包含n2k 个单元，每个单元有与它相关联的个单元，每个单元有与它相关联的l个变量，个变量，l 是是C中的符号的数目。
94、所以变量总数是中的符号的数目。所以变量总数是O(n2k)。qCELL的长度为的长度为O(n2k)。START的长度为的长度为O(nk)。qACCEPT的长度为的长度为O(n2k)。MOVE的长度为的长度为O(n2k)。79库克-列文定理推论推论推论推论7.327.323SAT 是是NP完全的。完全的。80主要内容主要内容7.1度量复杂性度量复杂性大大O 和小和小o 记法、分析算法、模型间的复杂性关系记法、分析算法、模型间的复杂性关系7.2P类类多项式时间、多项式时间、P 中的问题举例中的问题举例7.3NP类类NP中的问题举例、中的问题举例、P与与NP问题问题7.4NP完全性完全性多项式时间可归
95、约性、多项式时间可归约性、NP完全性的定义、库克完全性的定义、库克-列文定理列文定理7.5几个几个NP完全问题完全问题顶点覆盖问题、顶点覆盖问题、哈密顿路径问题哈密顿路径问题、子集和问题、子集和问题81几个NP完全问题推论推论推论推论7.337.33CLIQUE 是是NP完全的。完全的。q证明某语言是证明某语言是NP完全的，一般的策略是给出从完全的，一般的策略是给出从3SAT到该到该语言的多项式时间归约。语言的多项式时间归约。q在构造在构造3SAT到一个语言的多项式时间归约时，要寻找这个到一个语言的多项式时间归约时，要寻找这个语言中语言中能模拟布尔公式的变量和句子的结构能模拟布尔公式的变量和句
96、子的结构。定义定义定义定义7.277.27如果语言如果语言B 满足下面两个条件，就称为满足下面两个条件，就称为NP完全的完全的：1）B 属于属于NP，并且，并且2）NP中的每个中的每个A 都多项式时间可归约到都多项式时间可归约到B。82顶点覆盖问题q若若G 是无向图，则是无向图，则G 的的顶点覆盖顶点覆盖是结点的一个子集，使得是结点的一个子集，使得G 的每条边都与子集中的结点之一相关联。的每条边都与子集中的结点之一相关联。q顶点覆盖问题旨在确定图中是否存在指定规模的顶点覆盖。顶点覆盖问题旨在确定图中是否存在指定规模的顶点覆盖。VERTEX - COVER= |G 是具有是具有k 个结点的顶点覆
97、盖的无向图个结点的顶点覆盖的无向图定理定理定理定理7.347.34VERTEX COVER 是是NP完全的。完全的。83顶点覆盖问题定理定理定理定理7.347.34VERTEX - COVER是是NP完全的。完全的。证明：证明：给出一个从给出一个从3SAT 到到VERTEX COVER 的在多项式时间内运算的在多项式时间内运算的归约，该归约的归约，该归约把布尔公式把布尔公式 映射为一个图映射为一个图G 和值和值k 。对于。对于 中的每一个中的每一个变量变量 x，产生一条连接着两个结点的边。把这个构件中的两个结点标记为，产生一条连接着两个结点的边。把这个构件中的两个结点标记为x和和。把。把x赋值
98、为赋值为TRUE对应于顶点覆盖选择该边的左结点，而赋值对应于顶点覆盖选择该边的左结点，而赋值为为FALSE对应于右结点。对应于右结点。对应于子句的构件稍有点复杂。每个子句的构件是用该子句的三个文字标对应于子句的构件稍有点复杂。每个子句的构件是用该子句的三个文字标记的三个结点组成的三元组。记的三个结点组成的三元组。这三个结点互相连接这三个结点互相连接，并且与变量构件中具，并且与变量构件中具有相同标记的结点相连接。因此出现在有相同标记的结点相连接。因此出现在G中的结点总数是中的结点总数是2m +3l ，其中，其中 有有m 个变量和个变量和l 个子句。今个子句。今k 等于等于m +2l 。84顶点覆
99、盖问题 =( x1 x1 x2)()(x2x2)归约从归约从 产生产生G，k，k =8，x2x1x1x2x2x2x1 可满足当且仅当可满足当且仅当G 有有k 个节点的顶点覆盖。个节点的顶点覆盖。85顶点覆盖问题为证明该归约满足要求需要证明为证明该归约满足要求需要证明 可满足当且仅当可满足当且仅当G 有有k 个节点的顶点覆个节点的顶点覆盖。从一个满足赋盖。从一个满足赋值开始。首先把变量构件中对应于赋值中真文字的结点放入顶值开始。首先把变量构件中对应于赋值中真文字的结点放入顶点覆盖中。然后，在每个子句中挑选点覆盖中。然后，在每个子句中挑选一个真文字，把每个子句构件中剩下的两个一个真文字，把每个子句
100、构件中剩下的两个节点放入顶点覆盖中，现在共有节点放入顶点覆盖中，现在共有 k个结点。它们覆盖所有边，因为显然每个变量个结点。它们覆盖所有边，因为显然每个变量构件的边被覆盖了，在每个子句构件中的所有三条边也被覆盖了，所有介于变量构件的边被覆盖了，在每个子句构件中的所有三条边也被覆盖了，所有介于变量构件和子句构件之间的边也被覆盖了。所以构件和子句构件之间的边也被覆盖了。所以G 有有k 个结点的顶点覆盖。个结点的顶点覆盖。其次，如果其次，如果G有有 k个节点的顶点覆盖，通过构造满足赋值来证明个节点的顶点覆盖，通过构造满足赋值来证明是可满足是可满足的。为了覆盖变量构件的边和子句构件的三条边，顶点覆盖必
101、须包含每个变量构的。为了覆盖变量构件的边和子句构件的三条边，顶点覆盖必须包含每个变量构件的一个结点以及每个子句构件的两个结点。这就占用了全部顶点覆盖的节点，件的一个结点以及每个子句构件的两个结点。这就占用了全部顶点覆盖的节点，没有剩余的份额。选取变量构件中在顶点覆盖中的结点，把相应的文字赋值为没有剩余的份额。选取变量构件中在顶点覆盖中的结点，把相应的文字赋值为真。这个赋值满足真。这个赋值满足，因为连接变量构件和每个子句构件的三条边都被覆盖了，因为连接变量构件和每个子句构件的三条边都被覆盖了，而子句构件中只有两个结点在顶点覆盖中，所以其中一条边必定被变量构件中一而子句构件中只有两个结点在顶点覆盖
102、中，所以其中一条边必定被变量构件中一个结点覆盖，因此赋值满足相应的子句。个结点覆盖，因此赋值满足相应的子句。86哈密顿路径问题定理定理定理定理7.357.35HAMPATH 是是NP完全的。完全的。只需证明只需证明3SAT pHAMPATH。对于每个。对于每个3cnf 公式公式，我们说明怎么构造，我们说明怎么构造一个包含两个节点一个包含两个节点s和和t 的有向图的有向图G ，使得，使得s 和和t 之间存在哈密顿路径当之间存在哈密顿路径当且仅当且仅当 可满足。可满足。从包含从包含k 个子句的个子句的3cnf 公式公式 开始构造：开始构造： = (a1b1c1)(a2b2c2)(akbkck)其中
103、其中a，b，c是文字是文字xi 或或，设，设x1，xl 是是的的l 个变量。个变量。现在说明怎样把现在说明怎样把转换为图转换为图G。构造的图。构造的图G 使用不同的部分表示出现在使用不同的部分表示出现在中的变量和子句。中的变量和子句。把每个变量把每个变量xi 表示为一个包含一行水平结点的钻石形结构，把表示为一个包含一行水平结点的钻石形结构，把的每个子的每个子句表示为单个结点。句表示为单个结点。87哈密顿路径问题xi cj变量变量xi 表示为一个钻石形结构表示为一个钻石形结构把子句把子句cj 表示为结点表示为结点88哈密顿路径问题x1 c1x2c2c3ckxlstG 的高层结构的高层结构89哈密
104、顿路径问题xi c1 c2在钻石结构中的水平结构在钻石结构中的水平结构xi cj cj当子句当子句cj包含包含xi 时添加的边时添加的边90哈密顿路径问题xi cj cj当子句当子句cj包含包含 时添加的边时添加的边zig-zagzag-zig左左-右式和右右式和右-左式通过钻石，由满足赋值决定左式通过钻石，由满足赋值决定91哈密顿路径问题a1 a2 a3 b1 b292哈密顿路径问题定理定理定理定理7.367.36UHAMPATH 是是NP完全的。完全的。证明：对于包含结点证明：对于包含结点s 和和t 的有向图的有向图G ，归约构造包含结点，归约构造包含结点s和和t的无向的无向图图G。图。图
105、G 有从有从s 到到t 的哈密顿路径当且仅当的哈密顿路径当且仅当G有包含结点有包含结点s和和t的哈密顿的哈密顿路径。描述路径。描述G如下：如下：除了除了s 和和t 外，外，G 的每个结点的每个结点u 被替换为被替换为G的三个结点的三个结点uin，umid，uout。G的的节点节点s 和和t 被替换为被替换为G中的结点中的结点sout和和tin。G有两种类型的边。首先有连接有两种类型的边。首先有连接umid与与uin，umid和和uout的边。其次，如果的边。其次，如果G中有从中有从u到到v的边，则的边，则uout与与vin有边有边相连。这就完成了相连。这就完成了G的构造。的构造。通过证明通过证
106、明G有从有从s 到到t 的哈密顿路径当且仅当的哈密顿路径当且仅当G有从有从sout到到tin的哈密顿路径，的哈密顿路径，可以说明这种构造满足要求。为证明一个方向，注意到可以说明这种构造满足要求。为证明一个方向，注意到G中的哈密顿路径中的哈密顿路径P：s，u1，u2，uk，t93哈密顿路径问题定理定理定理定理7.367.36UHAMPATH 是是NP完全的。完全的。在在G中有一条对应的哈密顿路径中有一条对应的哈密顿路径P：sout，u1in，u1mid，u1out，u2in，u2mid，u2out，tin为证明另一个方向，我们断言为证明另一个方向，我们断言G中的任何从中的任何从sout到到tin
107、的哈密顿路径，都如同的哈密顿路径，都如同刚刚描述的路径刚刚描述的路径P那样，必定是从结点的一个三元组通向另一个三元组，那样，必定是从结点的一个三元组通向另一个三元组，起始与结束的地方除外。这就将完成本证明，因为这样的路径在起始与结束的地方除外。这就将完成本证明，因为这样的路径在G中都有对中都有对应的哈密顿路径。通过从结点应的哈密顿路径。通过从结点sout出发，跟踪该路径来证明本断言。注意到出发，跟踪该路径来证明本断言。注意到路径上的下一个结点必定是路径上的下一个结点必定是uiin，因为只有那些结点与，因为只有那些结点与sout相连。再下一个结相连。再下一个结点必定是点必定是uimid，因为在哈
108、密顿路径中，其他方式都不能包括，因为在哈密顿路径中，其他方式都不能包括uimid。在。在uimid以以后是后是uiout，因为这是，因为这是uimid连接到另一个唯一的结点。再下一个结点必定是连接到另一个唯一的结点。再下一个结点必定是ujin，因为没有别的结点可以连接到，因为没有别的结点可以连接到uiout。重复这种推理直到到达。重复这种推理直到到达tin为止。为止。94子集和问题定理定理定理定理7.377.37SUBSET-SUM 是是NP完全的。完全的。证明：证明：SUBSET-SUM NP，只需证明，只需证明3SATpSUBSET-SUM。设设是一个布尔公式，其变量是是一个布尔公式，其变
109、量是x1，xl，子句是，子句是c1，ck。归约把。归约把转转化为化为SUBSET-SUM问题的一个实例问题的一个实例S，t，其中，其中S 的元素和数的元素和数t 是图中以是图中以通常的十进制记法表示的行。双线上面的行标记为通常的十进制记法表示的行。双线上面的行标记为y1，z1，y2，z2，yl，zl和和g1，h1，g2，h2，gk，hk它们组成它们组成S的元素。双线下面的行是的元素。双线下面的行是t 。SUBSET-SUM =|s =x1,xk，且存在，且存在y1,yl x1,xk 使得使得 yi =t 95子集和问题-从从3SAT 到到pSUBSET-SUM 的归约的归约1234lc1c2c
110、ky1z1y2z2y3z3ylzl10000100001000100010010011100000010000010001000000g1h1g2h2gkhk100100101011t1111133396100010011000010010011001000010101000100011101001000110001000100100101011+11113333+x1x1+x2x2+x3x3+x4x41234子句子句 对应于对应于 10进位数字进位数字3CNF formula:Xk对应与YKXK对应ZK子句c1中至少一真，要使和为3,可能要补差额2，这里备用同上，为子句c4 备用补差 Dum
111、mies凑数的硬币子句c1C2C3c4子句号数c297100010011000010010011001000010101000100011101001000110001000100100101011+11113333+x1x1+x2x2+x3x3+x4x41234子句子句 对应于对应于 10进位数字进位数字3CNF formula:Xk对应与YKXK对应ZK子句c1中至少一真，要使和为3,可能要补差额2，这里备用同上，为子句c4 备用补差 dummies子句c1C2C3c4子句号数第2n-1和2n行中只保留一行，根据赋值选留，留下的每行10进位数是子集，和，是10进位数981000100110
112、00010010011001000010101000100011101001000110001000100100101011+11113333+x1y1x1Z1+x2y2x2Z2+x2y2x3Z3+x4y4x4Z41234子句号数 变量与数表的对应变量与数表的对应3CNF formula: 前L个1, 后K个 31表示每个Xi（或Xi）出现。给定合取式，造表只要多项式 时间 O(L+k)2) Dummies后面的gi hi表示x1出现在子句2中表示 x4出现在子句C4中99Subset Sum100010011000010010011001000010101000100011101001000
113、11000100010010010101111113333+x1x1+x2x2+x3x3+x4x4Note 1: The “1111”每列加起来为1,表示同一子句中Xi和xi中只用了其中为真的那一行，Note 2: 这块每列和为这块每列和为13,表示表示每子句三个元中至少一每子句三个元中至少一个为真，个为真，适当补充若干适当补充若干gi hi, 可使可使得每列和为得每列和为3100Subset Sum10001001100001001001100100001010100010001110100100011000100010010010101111113333+x1x1+x2x2+x3x3+x4
114、x4Note 1: The “1111”每列加起来为1,表示同一子句中Xi和xi中只用了其中为真的那一行，Note 2: 这块每列和为这块每列和为13,表示表示每子句三个元中至少一每子句三个元中至少一个为真，个为真，适当补充若干适当补充若干gi hi, 可使可使得每列和为得每列和为3101Subset Sum10001001100001001001100100001010100010001110100100011000100010010010101111113333+x1x1+x2x2+x3x3+x4x4Note 1: The “1111”每列加起来为1,表示同一子句中Xi和xi中只用了一个N
115、ote 2: 这块每列和为这块每列和为13,表示表示每子句三个元中至少一每子句三个元中至少一个为真，个为真，适当补充若干适当补充若干gi hi, 可使得每列和为可使得每列和为3凑数的硬币102设合取式满足，可选出xi yi如下其和为最后一行，对应一个子集和 是一个可 满足的赋值10001001100001001001100100001010100010001110100100011000100010010010101111113333100010011000010100011101001000100010010010111113333+x1x1+x2x2+x3x3+x4x4+用这里补差额总和根
116、据赋值， 选出来的行，10进位数（不是二进制，才能有3）103不满足加不够3 is not a satisfying assignment100010011000010010011001000010101000100011101001000110001000100100101011111133331000010010000101000111010010001000?11112?+x1x1+x2x2+x3x3+x4x4+子句C1 不满足，此列上面部分 无1, 全部加起来为2104Proof 3SAT P Subset Sum3SAT 归约为子集和问题q对每个对每个3合取范式合取范式 ,取总和（目
117、标）取总和（目标）t=1133（10进进制）以及按前面图找出来的数字集合制）以及按前面图找出来的数字集合S .（包括（包括yizi,gi,hi等等等等)q如果如果3SAT,（已经被满足）则如前原选出的（已经被满足）则如前原选出的yizi,gi,hi之和为之和为t,q反之，有了子集和的解，原可构造合取范式的满足指派反之，有了子集和的解，原可构造合取范式的满足指派105子集和问题现在说明这种构造为什么能满足要求，证明现在说明这种构造为什么能满足要求，证明可满足当且仅当可满足当且仅当S的某个的某个子集加来等于子集加来等于t 。假设假设可满足。如下构造可满足。如下构造S 的子集。在满足赋值中，如果的子
118、集。在满足赋值中，如果xi赋值赋值TRUE，就选择，就选择yi；如果；如果xi 赋值赋值FALSE，就选择，就选择zi。如果把已经选择的数。如果把已经选择的数加起来则头加起来则头l 位的每一位都是位的每一位都是1，因为对每个，因为对每个i 都选择都选择yi 或或zi 。而且，。而且，后后k 位的每一位都介于位的每一位都介于l和和3之间，因为每个子句都被满足，所以包含之间，因为每个子句都被满足，所以包含l到到3个真文字。现在进一步选择足够的个真文字。现在进一步选择足够的g 和和h 使得后使得后k 位的每一位都加位的每一位都加到到3，从而达到目标值。，从而达到目标值。假设假设S 的一个子集加起来等
119、于的一个子集加起来等于t 。在注意观察之后，构造一个。在注意观察之后，构造一个 的满的满足赋值。首先，足赋值。首先，S中成员的所有位都是中成员的所有位都是0或或1。其次，表中描述。其次，表中描述S 的每一列的每一列最多包含五个最多包含五个1。因此当。因此当S 的某个子集相加时，不会有到下一列的进位。的某个子集相加时，不会有到下一列的进位。为了在头为了在头l 列的每一列都得到列的每一列都得到1，子集对每个，子集对每个I 都必须包含都必须包含yi 或或zi ，但又不，但又不能同时包含二者。能同时包含二者。106子集和问题现在构造满足赋值。如果子集包含现在构造满足赋值。如果子集包含yi ，就赋，就赋
120、xi 为为TRUE，否，否则就赋它为则就赋它为FALSE。该赋值肯定满足。该赋值肯定满足，因为后，因为后k 列的每一列的每一列之和总是列之和总是3。在。在cj列，列，gj和和hj，最多提供，最多提供2，所以子集中的，所以子集中的yi 或或zi ，在该列必须至少提供，在该列必须至少提供1。如果是。如果是yi ，那么，那么，xi出现在出现在cj中而且赋值为中而且赋值为TRUE，所以，所以cj被满足。如果是被满足。如果是zi ，那么，那么出出现在现在cj而且而且xi赋值为赋值为FALSE，所以，所以cj也被满足。因此也被满足。因此被满被满足。足。最后，必须保证该归约可以在多项式时问内完成。表的尺最后
121、，必须保证该归约可以在多项式时问内完成。表的尺寸大约是寸大约是(k +l)2，每一格的内容都可以从任何，每一格的内容都可以从任何 中轻易地算中轻易地算出来。所以全部时间是出来。所以全部时间是O(n2)个简单步骤个简单步骤。107使用时，直接删除本页！使用时，直接删除本页！精品课件，你值得拥有精品课件，你值得拥有！精品课件，你值得拥有精品课件，你值得拥有！108使用时，直接删除本页！使用时，直接删除本页！精品课件，你值得拥有精品课件，你值得拥有！精品课件，你值得拥有精品课件，你值得拥有！109使用时，直接删除本页！使用时，直接删除本页！精品课件，你值得拥有精品课件，你值得拥有！精品课件，你值得拥有精品课件，你值得拥有！110作业q7.1、7.2、7.5、7.9、7.36、7.39、7.407.29、7.30111
