计算理论导引--时间复杂性qhv.pptx

朴秀峰朴秀峰计算理论1引言qChurch-Turing论题论题：能够用总停机的：能够用总停机的Turing机计算的函数机计算的函数和识别的语言是可计算的（可判定的）；和识别的语言是可计算的（可判定的）；理论可计算理论可计算q计算复杂性理论计算复杂性理论研究计算模型在各种资源（主要是研究计算模型在各种资源（主要是时间时间、空间空间等）限制下的计算能力；等）限制下的计算能力；实际可计算实际可计算q一个可以计算的问题一个可以计算的问题需要多少时间和空间？需要多少时间和空间？q64层次梵塔，层次梵塔，1秒钟移动秒钟移动1000片（计算机作），要多少时间片（计算机作），要多少时间？q(264-1)/1000=5.846亿年亿年2引言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亿世纪亿世纪1.3*1013世纪世纪3引言Complexity：Hamilton回路问题（回路问题（HC）：任给一个无向图）：任给一个无向图G，问，问G中有中有Hamilton回路吗？回路吗？Hamilton回路是指经过每一个顶点且每一个顶点只经过一次的回路。回路是指经过每一个顶点且每一个顶点只经过一次的回路。q设设G有有n个顶点，由于回路没有始点和终点，可以任意定一个顶点作为排列的第个顶点，由于回路没有始点和终点，可以任意定一个顶点作为排列的第一个顶点，共有（一个顶点，共有（n-1）！个排列。当）！个排列。当n=25时，时，24！=6.2*1023.假设用一台超级假设用一台超级计算机计算，每秒可以检查计算机计算，每秒可以检查1亿个排列。每年有亿个排列。每年有3.15*107秒，不停地工作，每年秒，不停地工作，每年可以检查可以检查3.15*1015个排列。检查完所有的排列需要个排列。检查完所有的排列需要1.97*108年，即年，即1亿亿9千千7百百年！年！q计算复杂性理论就是要研究计算模型在各种资源限制下的计算能力。将问题划计算复杂性理论就是要研究计算模型在各种资源限制下的计算能力。将问题划分成分成HardandEasy两大类。两大类。4引言co-TM recognizable（补集可识）TM-recognizable TM decidable PSPACE co-NPNP P5主要内容主要内容7.1度量复杂性度量复杂性大大O 和小和小o 记法、分析算法、模型间的复杂性关系记法、分析算法、模型间的复杂性关系7.2P类类多项式时间、多项式时间、P 中的问题举例中的问题举例7.3NP类类NP中的问题举例、中的问题举例、P与与NP问题问题7.4NP完全性完全性多项式时间可归约性、多项式时间可归约性、NP完全性的定义、库克完全性的定义、库克-列文定理列文定理7.5几个几个NP完全问题完全问题顶点覆盖问题、哈密顿路径问题、子集和问题顶点覆盖问题、哈密顿路径问题、子集和问题6度量复杂性q考察下列例子：考察下列例子：语言语言A=0k1k|k0，显然，显然A是一个可判定的语言。是一个可判定的语言。考察下面判定考察下面判定A的单带的单带TMM1M1=“对于输入串对于输入串w：1)扫描带子，如果在扫描带子，如果在1的右边发现的右边发现0，就，就拒绝拒绝。2)如果带上既有如果带上既有0也有也有1，就重复下一步。，就重复下一步。3)扫描带子，删除一个扫描带子，删除一个0和一个和一个1。4)如果所有如果所有1都被删除以后还有都被删除以后还有0，或者所有，或者所有0都被删除以后还有都被删除以后还有1，就，就拒绝拒绝。否则，如果在带上既没有剩下。否则，如果在带上既没有剩下0也没有剩下也没有剩下1，就，就接接受受。q考察判定考察判定A的图灵机的图灵机M1的算法所需的时间。的算法所需的时间。7度量复杂性q把把算法的运行时间算法的运行时间纯粹作为表示纯粹作为表示输入字符串的长度输入字符串的长度来计算，来计算，而不考虑其它参数。而不考虑其它参数。q最坏情况分析（最坏情况分析（worst-caseanalysis）：考虑在某特定长度：考虑在某特定长度的所有输入上的最长运行时间。的所有输入上的最长运行时间。q平均情况分析（平均情况分析（average-caseanalysis）：考虑在某特定长：考虑在某特定长度的所有输入上的运行时间的平均值。度的所有输入上的运行时间的平均值。8度量复杂性定义定义定义定义7.17.1令令M 是一个在所有输入上都停机的确定型图灵机。是一个在所有输入上都停机的确定型图灵机。M 的的运行时间运行时间或者或者时间复杂度时间复杂度，是一个函数，是一个函数f:NN，其中，其中N 是非负整数集合，是非负整数集合，f(n)是是M 在在所有长度为所有长度为n 的输入上运行时所经过的最大步数的输入上运行时所经过的最大步数。若若f(n)是是M 的运行时间，则称的运行时间，则称M 在时间在时间f(n)内运内运行，行，M 是时间图灵机。是时间图灵机。通常使用通常使用n 表示输入的长度。表示输入的长度。9渐进分析q因为算法的精确运行时间通常是一个复杂的表达式，所以因为算法的精确运行时间通常是一个复杂的表达式，所以一般是估计它的趋势和级别。一般是估计它的趋势和级别。q通过一种称为通过一种称为渐进分析渐进分析(asymptoticanalysis)的方便的估的方便的估计形式，可以试图了解算法在长输入上的运行时间。计形式，可以试图了解算法在长输入上的运行时间。q只考虑算法运行时间的表达式的最高项，而忽略该项的系只考虑算法运行时间的表达式的最高项，而忽略该项的系数和其它低次项，因为在在长输入上，数和其它低次项，因为在在长输入上，最高次项最高次项的影响相的影响相比其它项比其它项占据主导地位占据主导地位。q例如，函数例如，函数f(n)=6n3+2n2+20n+45称称f 渐进地不大于渐进地不大于n3，表达这种关系的，表达这种关系的渐进记法渐进记法或大或大O 记记法法是是f(n)=O(n3)。10大 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)的渐近上界，的渐近上界，以强调没有考虑常以强调没有考虑常数因子。数因子。11大 O 和小 o 记法例例7.3f1(n)是函数是函数5n3+2n2+22n+6。保留最高次项。保留最高次项5n3，并且，并且舍去它的系数舍去它的系数5，得到，得到f1=O(n3)。验证该结果是否满足上面的形式定义。验证该结果是否满足上面的形式定义。令令c=6，n0=10，则对于，则对于所有所有n10，有，有5n3+2n2+22n+66n3。此外，有此外，有f1=O(n4)，因为，因为n4比比n3大，它也是大，它也是f1的一个渐近的一个渐近上界。上界。但是但是f1不等于不等于O(n2)，不论给，不论给c 和和n0赋什么值，始终不满足赋什么值，始终不满足定义的要求。定义的要求。12大 O 和小 o 记法例例7.4大大O记法以一种特别的方式与对数相互影响。记法以一种特别的方式与对数相互影响。通常写对数时必须指明基数通常写对数时必须指明基数(或称为对数的底或称为对数的底)，如，如x=log2n。这里基数这里基数2表明该等式等价于等式表明该等式等价于等式2x=n。logbn 的值随着基数的值随着基数b 的改变而乘以相应的常数倍，因为有恒等式的改变而乘以相应的常数倍，因为有恒等式logbn=log2n/log2b。所以，写。所以，写f(n)=O(logn)时不必再指明基数，因为最终时不必再指明基数，因为最终要忽略常数因子。要忽略常数因子。13大 O 和小 o 记法q令令f2(n)是函数是函数3nlog2n+5nlog2log2n+2。此时此时f2(n)=O(nlogn)，因为，因为 logn 比比loglogn更占支配位置。更占支配位置。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)代表不超过某个固代表不超过某个固定常数的上界。定常数的上界。14大O 和小o 记法q我们经常导出我们经常导出nc 的界，的界，c 是大于是大于0的常数。这种界称为的常数。这种界称为多多项式界项式界(polynamialbound)。形如。形如的界，当的界，当 是大于是大于0的实数时，称为的实数时，称为指数界指数界(exponentialbound)。q大大O 记法记法指一个函数渐近地指一个函数渐近地不大于不大于另一个函数。另一个函数。q小小o 记法记法是渐进的是渐进的小于小于另一个函数。另一个函数。q大大O记法与小记法与小o记法的区别类似于记法的区别类似于和之间的区别。和之间的区别。15大O 和小o 记法定义定义定义定义7.57.5设设f 和和g 是两个函数是两个函数f,g:N R+，如果，如果则称则称f(n)=o(g(n)。换言之，。换言之，f(n)=o(g(n)意味意味着对于任何实数着对于任何实数c0，存在一个数，存在一个数n0，使得对所，使得对所有有nn0，f(n)cg(n)。16大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)。17分析算法分析语言分析语言A=0k1k|k0对应的图灵机算法。对应的图灵机算法。M1=“对于输入串对于输入串w：1)扫描带子，如果在扫描带子，如果在1的右边发现的右边发现0，就，就拒绝拒绝。2)如果带上既有如果带上既有0也有也有1，就重复下一步。，就重复下一步。3)扫描带子，删除一个扫描带子，删除一个0和一个和一个1。4)如果所有如果所有1都被删除以后还有都被删除以后还有0，或者所有，或者所有0都被删除以后还有都被删除以后还有1，就就拒绝拒绝。否则，如果在带上既没有剩下。否则，如果在带上既没有剩下0也没有剩下也没有剩下1，就，就接受接受。q步骤步骤1中，机器扫描带以验证输入的形式是中，机器扫描带以验证输入的形式是0*1*。执行这次扫描需要。执行这次扫描需要n步步。读写头重新放置在带的左端另外需要读写头重新放置在带的左端另外需要n步步。共需要。共需要2n步步。即。即O(n)步。步。q在步骤在步骤2和和3中，机器反复扫描带，在每一次扫描中删除一个中，机器反复扫描带，在每一次扫描中删除一个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)。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，如何？，如何？19分析 M2 的时间复杂性q下面机器下面机器M2采用不同的方法，可以更快地判定采用不同的方法，可以更快地判定A。ATIME(nlogn)。M2=“对输入串对输入串w：1)扫描带，如果扫描带，如果1的右边发现的右边发现0，就，就拒绝拒绝。2)只要在带上还有只要在带上还有0和和1，就重复下面的步骤。，就重复下面的步骤。3)扫描带，检查剩余的扫描带，检查剩余的0和和1的总数是偶数还是奇数。的总数是偶数还是奇数。若是奇数，就若是奇数，就拒绝拒绝。4)再次扫描带，从第一个再次扫描带，从第一个0开始，开始，隔一个删除一个隔一个删除一个0；然后从第一个然后从第一个1开始，开始，隔一个删除一个隔一个删除一个1.5)如果带上不再有如果带上不再有0和和1，就，就接受接受。否则。否则拒绝拒绝。”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)。这个结果在单带图灵机上不可能进一步改进。这个结果在单带图灵机上不可能进一步改进。q单带图灵机在单带图灵机在o(nlogn)时间内判定的语言都是正则语言时间内判定的语言都是正则语言。20分析M3的时间复杂性q如果图灵机有第二条带，就可以在如果图灵机有第二条带，就可以在O(n)时间（也称为线性时间）内判定语时间（也称为线性时间）内判定语言言A。下面的两带图灵机。下面的两带图灵机TMM3在线性时间内判定在线性时间内判定A。M3=“对于输入串对于输入串w：1)扫描带，如果扫描带，如果1的右边发现的右边发现0，就，就拒绝拒绝。2)扫描带扫描带1上的上的0，直到第一个，直到第一个1时停止，同时把时停止，同时把0复制到带复制到带2上。上。3)扫描带扫描带1上的上的1直到输入的末尾。每次从带直到输入的末尾。每次从带1上读到一个上读到一个1，就在带，就在带2上删除一个上删除一个0，如果在读完，如果在读完1之前所有的之前所有的0都被删除，就都被删除，就拒绝拒绝。4)如果所有如果所有0都被删除，就都被删除，就接受接受。如果还有。如果还有0剩下，就剩下，就拒绝拒绝。”q四个步骤中每一步需要四个步骤中每一步需要O(n)步，所以全部的运行时间是步，所以全部的运行时间是O(n)，因而是线，因而是线性的。性的。q注意，这可能是最好的运行时间，因为光是读输入就需要注意，这可能是最好的运行时间，因为光是读输入就需要n步。步。21A 的 C 程序A=0k1k|k=0,1,2,.先用用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)时间.使用的资源:随机存取,数组，两带图灵机，22总结 A 的运行时间q给出一个单带给出一个单带TMM1，能够在时间，能够在时间O(n2)内判定内判定A，以及一，以及一个更快的单带个更快的单带TMM2，能够在时间，能够在时间O(nlogn)内判定内判定A。两。两带带TMM3能在能在O(n)时间内判定语言时间内判定语言A。q因此因此A在单带在单带TM上的时间复杂度是上的时间复杂度是O(nlogn)，在两带，在两带TM上是上是O(n)。q注意注意A的复杂度与选择的计算模型有关。的复杂度与选择的计算模型有关。23复杂性理论与可计算性理论的区别q在在可计算性理论可计算性理论中，丘奇中，丘奇-图灵论题断言，图灵论题断言，所有合理的计算所有合理的计算模型都是等价的模型都是等价的，即它们所判定的语言类都是相同的。，即它们所判定的语言类都是相同的。q在在复杂性理论复杂性理论中，中，模型的选择影响语言的时间复杂度模型的选择影响语言的时间复杂度。如。如在一个模型上线性时间内可判定的语言，在另一个模型上在一个模型上线性时间内可判定的语言，在另一个模型上就不一定是线性时间内可判定的。就不一定是线性时间内可判定的。q在复杂性理论中，在复杂性理论中，根据计算问题的时间复杂度来对问题分根据计算问题的时间复杂度来对问题分类类。24模型间的复杂性关系定理定理定理定理7.87.8设设t(n)是一个函数，是一个函数，t(n)n。则每一个时间。则每一个时间t(n)的的多带多带图灵机都和某一个图灵机都和某一个O(t2(n)时间的时间的单带单带图灵图灵机等价。机等价。S 用它的一条带表示用它的一条带表示M 的所有的所有k条带条带的内容。这些带连续存放，的内容。这些带连续存放，M 的读的读写头的位置都标在恰当的方格上。写头的位置都标在恰当的方格上。01010Maaaba#01010#aaa#ba#S25模型间的复杂性关系01010Maaaba#01010#aaa#ba#S开始时，开始时，S 让它的带形成表示让它的带形成表示M 的所有带的格式，然后模拟的所有带的格式，然后模拟M 的步骤。的步骤。为了模拟为了模拟M 的一步，的一步，S 扫描带上的所有信息，扫描带上的所有信息，确定在确定在M 的读写头下的符的读写头下的符号号。然后。然后S 再次扫描带，再次扫描带，更新带内容和读写头位置更新带内容和读写头位置。如果。如果M 的读写头向右的读写头向右移动到带上以前没有读到的位置，那么移动到带上以前没有读到的位置，那么S 必须增加分配给这条带的存储空必须增加分配给这条带的存储空间。为此，它把自己的带的一部分向右移动一格。间。为此，它把自己的带的一部分向右移动一格。26模型间的复杂性关系01010Maaaba#01010#aaa#ba#S模拟模拟M 的每一步，的每一步，S执行两次扫描，执行两次扫描，还可能最多向右移动还可能最多向右移动k次。次。每一次用时每一次用时O(t(n)，所以，模拟，所以，模拟M 的一步操作，的一步操作，S总共耗时总共耗时O(t(n)。现在，来界定模拟所需要的全部时间。在开始阶段，现在，来界定模拟所需要的全部时间。在开始阶段，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(n)，证毕。，证毕。27模型间的复杂性关系定义定义定义定义7.97.9设设N 是一个非确定型图灵机，并且是一个判定机。是一个非确定型图灵机，并且是一个判定机。N 的运行时间是函数的运行时间是函数f:NN，其中其中 f(n)是在任何是在任何长度为长度为n 的输入上所有的计算分支中最大步数的输入上所有的计算分支中最大步数。28模型间的复杂性关系定理定理定理定理7.107.10设设t(n)是一个函数，是一个函数，t(n)n。则每一个。则每一个t(n)时间时间的的非确定型单带图灵机非确定型单带图灵机都与某一都与某一2O(t(n)时间时间的确定的确定型图灵机型图灵机等价。等价。设设N是一个在时间是一个在时间t(n)内运行的非确定型内运行的非确定型TM，构造确定型，构造确定型TMD，D通过搜索通过搜索N 的非确定型计算树来模拟的非确定型计算树来模拟N。在长度为在长度为n的输入上，的输入上，N的非确定型计算树的非确定型计算树的的每一个分支的长度最多是每一个分支的长度最多是t(n)，树的，树的每一个结点最多有每一个结点最多有b个子女个子女，其中，其中b是是N 的转移函数所决定的合法选择的最大值。因此的转移函数所决定的合法选择的最大值。因此树叶的总数最多是树叶的总数最多是bt(n)。0010Dxx#01x12332312113输入带模拟带地址带29模型间的复杂性关系模拟过程以宽度优先法探查这棵树。换句话说，在访问深度为模拟过程以宽度优先法探查这棵树。换句话说，在访问深度为d+1的结点之前，的结点之前，先访问所有深度为先访问所有深度为d 的结点。的结点。树中结点的总数小于最大叶数的两倍，因此用树中结点的总数小于最大叶数的两倍，因此用O(bt(n)作它的上界。作它的上界。从根出发下行到一个结点的时间是从根出发下行到一个结点的时间是O(t(n)。因此，因此，D的运行时间是的运行时间是O(t(n)bt(n)=2O(t(n)。TMD有三条带。把它转变为单带有三条带。把它转变为单带TM，最多使运行时间乘方。这样，单带模，最多使运行时间乘方。这样，单带模拟机的运行时间是拟机的运行时间是(2O(t(n)2=2O(2t(n)=2O(t(n)，定理得证。，定理得证。0010Dxx#01x12332312113输入带模拟带地址带30主要内容主要内容7.1度量复杂性度量复杂性大大O 和小和小o 记法、分析算法、模型间的复杂性关系记法、分析算法、模型间的复杂性关系7.2P类类多项式时间、多项式时间、P 中的问题举例中的问题举例7.3NP类类NP中的问题举例、中的问题举例、P与与NP问题问题7.4NP完全性完全性多项式时间可归约性、多项式时间可归约性、NP完全性的定义、库克完全性的定义、库克-列文定理列文定理7.5几个几个NP完全问题完全问题顶点覆盖问题、哈密顿路径问题、子集和问题顶点覆盖问题、哈密顿路径问题、子集和问题31多项式时间q定理定理7.8和定理和定理7.10显示出一个重要的差别。一方面，问题的时间复杂性显示出一个重要的差别。一方面，问题的时间复杂性在在确定型单带和多带图灵机确定型单带和多带图灵机上最多是平方或上最多是平方或多项式多项式的差异；另一方面，的差异；另一方面，在在确定型和非确定型图灵机确定型和非确定型图灵机上，问题的时间复杂性最多是上，问题的时间复杂性最多是指数指数差异。差异。q典型的指数时间算法来源于通过搜索解空间来求解问题，这称为典型的指数时间算法来源于通过搜索解空间来求解问题，这称为蛮力搜蛮力搜索（索（brute-forcesearch）。例如，分解一个数为素数因子的一种方法是。例如，分解一个数为素数因子的一种方法是搜遍所有可能的因子。搜索空间的规模是指数的，所以这种搜索需要指搜遍所有可能的因子。搜索空间的规模是指数的，所以这种搜索需要指数时间。有时候，通过更深入地理解问题，可以避免蛮力搜索，从而可数时间。有时候，通过更深入地理解问题，可以避免蛮力搜索，从而可能会找到更实用的多项式时间算法。能会找到更实用的多项式时间算法。q所有合理的确定型计算模型都是所有合理的确定型计算模型都是多项式等价的（多项式等价的（polynomiallyequivalent），也就是说，它们中任何一个模型都可以模拟另一个，而运，也就是说，它们中任何一个模型都可以模拟另一个，而运行时间只增长多项式倍。行时间只增长多项式倍。当称所有合理的确定型模型都多项式等价时当称所有合理的确定型模型都多项式等价时，它足够广泛，它足够广泛，能容纳那些和实际计算机运行时间近似的模型能容纳那些和实际计算机运行时间近似的模型。例如，定。例如，定理理7.8表明确定型单带和多带固灵机模型是多项式等价的。表明确定型单带和多带固灵机模型是多项式等价的。32多项式时间在理论中，在理论中，P类扮演核心的角色，它的重要性在于：类扮演核心的角色，它的重要性在于：1)对于所有与确定型单带图灵机多项式等价的计算模型来说，对于所有与确定型单带图灵机多项式等价的计算模型来说，P是不变的。是不变的。2)P大致对应于在计算机上实际可解的那一类问题。大致对应于在计算机上实际可解的那一类问题。第第1条表明，在数学上，条表明，在数学上，P是一个稳健的类，它不受所采用的具体计算模型是一个稳健的类，它不受所采用的具体计算模型的影响。的影响。第第2条表明，从实用的观点看，条表明，从实用的观点看，P是恰当的。当一个问题在是恰当的。当一个问题在P中的时候，就有中的时候，就有办法在时间办法在时间nk(k是常数是常数)内求解它。至于这么长时间是否实用就依赖于内求解它。至于这么长时间是否实用就依赖于k和和实际的应用情况。实际的应用情况。定义定义定义定义7.117.11P是是确定型单带图灵机确定型单带图灵机在在多项式时间内可判定多项式时间内可判定的语言的语言类。换言之，类。换言之，PTIME(nk)33P中的问题举例q当给出多项式时间算法时，给出的是算法的高层描述，没有当给出多项式时间算法时，给出的是算法的高层描述，没有提及计算模型的特点，这样做回避了带和读写头运动的繁琐提及计算模型的特点，这样做回避了带和读写头运动的繁琐细节。细节。q分析一个算法，证明它在多项式时间内运行，需要两步：分析一个算法，证明它在多项式时间内运行，需要两步：1)必须为算法在长为必须为算法在长为n 的输入上运行时所需要的步骤给出多的输入上运行时所需要的步骤给出多项式上界（一般用大项式上界（一般用大O 记法）。记法）。2)必须考虑算法描述中的每一步，保证它们都可以由合理的必须考虑算法描述中的每一步，保证它们都可以由合理的确定型模型在多项式时间内实现。确定型模型在多项式时间内实现。q需要注意的问题所用的编码方法。合理的方法就是允许在多需要注意的问题所用的编码方法。合理的方法就是允许在多项式时间内把对象编码项式时间内把对象编码/解码为自然的内部表示或其它合理的解码为自然的内部表示或其它合理的编码。编码。q图的一种合理编码是它的结点和边的序列。另一种是相邻矩图的一种合理编码是它的结点和边的序列。另一种是相邻矩阵，其中若从结点阵，其中若从结点i 到结点到结点j有边，则第有边，则第(i,j)项为项为1，否，否则为则为0。34P中的问题举例-PATH有向图有向图G 包含结点包含结点s 和和t，如图所示。，如图所示。PATH问题问题就是要就是要确定是否存在从确定是否存在从s 到到t 的有向路径的有向路径。PATH=|G 是具有从是具有从s 到到t 的有向路径的有向图的有向路径的有向图st35P中的问题举例-PATH定理定理定理定理7.127.12PATHP 证明思路：证明思路：通过给出判定通过给出判定PATH的多项式时间算法来证明该定理。的多项式时间算法来证明该定理。PATH 的蛮力算法的蛮力算法通过通过考察考察G 中所有可能路径来确定是否存在从中所有可能路径来确定是否存在从s 到到t 的的有向路径有向路径。一条可能路径就是一条可能路径就是G 中长度最多为中长度最多为m 的结点序列，的结点序列，m 是是G 中的节点数。中的节点数。但是这些可能的路径数是但是这些可能的路径数是mm，这是，这是G 中结点数的指数倍。因此该蛮力算中结点数的指数倍。因此该蛮力算法消耗指数时间。法消耗指数时间。为了获得为了获得PATH 的多项式时间算法，必须设法避免蛮力搜索。一种方法是的多项式时间算法，必须设法避免蛮力搜索。一种方法是采用图搜索方法，如宽度优先搜索。连续标记采用图搜索方法，如宽度优先搜索。连续标记G 中从中从s 出发，长度为出发，长度为1,2,3直到直到m 的有向路径可达的所有节点。的有向路径可达的所有节点。用多项式可以容易地来界定该策略的运行时间。用多项式可以容易地来界定该策略的运行时间。36PATHPPATH 的一个多项式时间算法的一个多项式时间算法M 运行如下：运行如下：M“对输入对输入G,s,t，G是包含结点是包含结点s 和和t 的有向图：的有向图：1)在结点在结点s 上做标记。上做标记。2)复重下面步骤复重下面步骤3，直到不再有结点被标记。，直到不再有结点被标记。3)扫描扫描G 的所有边。如果找到一条边的所有边。如果找到一条边(a,b)，a 被标记，被标记，而而b 没有被标记，那么标记没有被标记，那么标记b。4)若若t 被标记，则被标记，则接受接受；否则，；否则，拒绝拒绝。”步骤步骤1和和4只执行一次只执行一次。步骤步骤3最多执行最多执行m 次次，因为除最后一次外，每一，因为除最后一次外，每一次执行都要标记次执行都要标记G 中的一个未标记的结点。所以用到的总步数最多是中的一个未标记的结点。所以用到的总步数最多是1+1+m，是，是G 的规模的多项式。的规模的多项式。M 的步骤的步骤1和和4很容易用任问合理的确定型模型在多项式时间内实现。步很容易用任问合理的确定型模型在多项式时间内实现。步骤骤3需要扫描输入，检查某些结点是否被标记，这也容易在多项式时间内需要扫描输入，检查某些结点是否被标记，这也容易在多项式时间内实现。所以实现。所以M 是是PATH 的多项式时间算法。的多项式时间算法。37P中的问题举例-RELPRIMERELPRIME 代表检查两个数是否是互素问题。代表检查两个数是否是互素问题。RELPRIME=|x 与与y 互素互素定理定理定理定理7.137.13RELPRIMEP 解决该问题的一种算法是搜索这两个数的所有可能的公因子。如果没有发现解决该问题的一种算法是搜索这两个数的所有可能的公因子。如果没有发现大于大于1的公因子，就接受。然而，用二进制或其它任何以的公因子，就接受。然而，用二进制或其它任何以k 为基的记法为基的记法(k2)表示的数字的大小是它表示长度的指数倍。因此该蛮力算法需要搜表示的数字的大小是它表示长度的指数倍。因此该蛮力算法需要搜遍指数多个可能的因子，消耗指数的运行时间。遍指数多个可能的因子，消耗指数的运行时间。改用一种古老的数值计算过程来求解该问题，称为改用一种古老的数值计算过程来求解该问题，称为欧几里德算法欧几里德算法(Euclideanalgorithm)，来计算最大公因子。两个自然数的，来计算最大公因子。两个自然数的最大公因子最大公因子(greatestcommondivisor)，即为，即为gcd(x,y)，能同时整除，能同时整除x 和和y 的最大整数。的最大整数。38RELPRIMEP证明证明:欧几里德算法欧几里德算法E 如下：如下：E=“对输入对输入，x 和和y 是二进制表示的自然数：是二进制表示的自然数：1)重复下面的操作，直到重复下面的操作，直到y=0.2)赋值赋值x x mody3)交换交换x和和y4)输出输出x。”显然，若显然，若E 在多项式时间内运行且正确，则在多项式时间内运行且正确，则R 也在多项式时间内运行且正也在多项式时间内运行且正确。所以只需分析确。所以只需分析E 的时间和正确性。的时间和正确性。步骤步骤2的每一次执行的每一次执行(除了第一次有可能例外除了第一次有可能例外)，都把，都把x 的值至少减少一半。的值至少减少一半。每一次执行步骤每一次执行步骤3都使都使x 和和y 的值相互交换，所以每两次循环就使得的值相互交换，所以每两次循环就使得x 和和y原先的值至少减少一半。于是步骤原先的值至少减少一半。于是步骤2和和3执行的最大次数是执行的最大次数是2log2x 和和2log2y 中较小的那一个。这两个对数与表示的长度成正比，步骤的执行次数是中较小的那一个。这两个对数与表示的长度成正比，步骤的执行次数是O(n)。E 的每一步仅消耗多项式时间，所以整个运行时间是多项式的。的每一步仅消耗多项式时间，所以整个运行时间是多项式的。算法算法R以以E为子程序求解为子程序求解RELPRIMER=“对输入对输入，x 和和y 是二进制表示的自然数：是二进制表示的自然数：1)在在上运行上运行E。2)若结果为若结果为1，就，就接受接受；否则；否则拒绝拒绝。”39P中的问题举例-上下文无关语言定理定理定理定理7.147.14每一个上下文无关语言都是每一个上下文无关语言都是P的成员。的成员。证明思路：证明思路：定理定理4.8证明了每一个证明了每一个CFL是可判定的，并且为每一个是可判定的，并且为每一个CFL给出了判定算法。如果那个算法在多项式时间内运行，那么本定理作为推给出了判定算法。如果那个算法在多项式时间内运行，那么本定理作为推论就必然成立。回忆那个算法，看它运行得是否够快。论就必然成立。回忆那个算法，看它运行得是否够快。令令L是一个由是一个由CFGG 产生的产生的CFG，G 是乔姆斯基范式。由问题是乔姆斯基范式。由问题2.26知：因知：因G是乔姆斯基范式，是乔姆斯基范式，任何得到字符串任何得到字符串w的推导都有的推导都有2n-1步步，n 是是w 的长度。当给的长度。当给L的判定机输入长为的判定机输入长为n的字符串时，它的字符串时，它通过试遍所有可能的通过试遍所有可能的2n-1步推导来判定步推导来判定L。如果其中有一个得到。如果其中有一个得到w 的推导，该判定机就接受；的推导，该判定机就接受；否则，就拒绝。否则，就拒绝。分析一下该算法可知，它不能在多项式时间内运行。分析一下该算法可知，它不能在多项式时间内运行。k 步推导的数量步推导的数量可能达到可能达到k 的指数，所以该算法可能需要指数时间。的指数，所以该算法可能需要指数时间。40P中的问题举例-上下文无关语言为了获得多项式时间算法，在此介绍一种强有力的技术，称为为了获得多项式时间算法，在此介绍一种强有力的技术，称为动态规划动态规划。这种技术通过累积小的子问题的信息来解决大的问题。把子问题的解都记这种技术通过累积小的子问题的信息来解决大的问题。把子问题的解都记录下来，这样就只需对它求解一次。为此，把所有了问题编成一张表，当录下来，这样就只需对它求解一次。为此，把所有了问题编成一张表，当碰到它们时，把它们的解系统地填入表格。碰到它们时，把它们的解系统地填入表格。在本例中，考虑在本例中，考虑G 的每一个变元是否产生的每一个变元是否产生w 的每一个子串这样的子问题。的每一个子串这样的子问题。算法把子问题的解填入一张算法把子问题的解填入一张nn表格。对于表格。对于ij，表的第，表的第(i,j)项包含产生项包含产生子串子串wiwi+1wj 的所有变元。的所有变元。ij 的表项没有使用。的表项没有使用。算法为算法为w 的每一子串填写表项。首先为长为的每一子串填写表项。首先为长为1的子串填写表项，然后是长的子串填写表项，然后是长为为2的子串，依此类推。它利用短子串的表顶内容来辅助确定长子串的表的子串，依此类推。它利用短子串的表顶内容来辅助确定长子串的表项内容。项内容。41P中的问题举例-上下文无关语言例如，假定该算法已经确定了由哪些变元产生所有长度不超过例如，假定该算法已经确定了由哪些变元产生所有长度不超过k 的的子串。为了确定变元子串。为了确定变元A 是否产生某一长为是否产生某一长为k+1的子串，算法把该子串以的子串，