计算理论导引-7-时间复杂性

1朴秀峰[e-mail]计算理论2引言Church-Turing论题：能够用总停机的Turing机计算的函数和识别的语言是可计算的（可判定的）；理论可计算计算复杂性理论研究计算模型在各种资源（主要是时间、空间等）限制下的计算能力；实际可计算一个可以计算的问题需要多少时间和空间？64层次梵塔，1秒钟移动1000片（计算机作），要多少时间？(264-1)/1000=5.846亿年3引言复杂度和时间：每秒作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世纪4引言Complexity：Hamilton回路问题（HC）：任给一个无向图G，问G中有Hamilton回路吗？Hamilton回路是指经过每一个顶点且每一个顶点只经过一次的回路。设G有n个顶点，由于回路没有始点和终点，可以任意定一个顶点作为排列的第一个顶点，共有（n-1）！个排列。当n=25时，24！=6.2*1023.假设用一台超级计算机计算，每秒可以检查1亿个排列。每年有3.15*107秒，不停地工作，每年可以检查3.15*1015个排列。检查完所有的排列需要1.97*108年，即1亿9千7百年！计算复杂性理论就是要研究计算模型在各种资源限制下的计算能力。将问题划分成HardandEasy两大类。5引言co-TMrecognizable（补集可识）TM-recognizableTMdecidablePSPACEco-NPNPP6主要内容7.1度量复杂性大O和小o记法、分析算法、模型间的复杂性关系7.2P类多项式时间、P中的问题举例7.3NP类NP中的问题举例、P与NP问题7.4NP完全性多项式时间可归约性、NP完全性的定义、库克-列文定理7.5几个NP完全问题顶点覆盖问题、哈密顿路径问题、子集和问题7度量复杂性考察下列例子：语言A={0k1k|k≥0}，显然A是一个可判定的语言。考察下面判定A的单带TMM1M1=“对于输入串w：1)扫描带子，如果在1的右边发现0，就拒绝。2)如果带上既有0也有1，就重复下一步。3)扫描带子，删除一个0和一个1。4)如果所有1都被删除以后还有0，或者所有0都被删除以后还有1，就拒绝。否则，如果在带上既没有剩下0也没有剩下1，就接受。考察判定A的图灵机M1的算法所需的时间。8度量复杂性把算法的运行时间纯粹作为表示输入字符串的长度来计算，而不考虑其它参数。最坏情况分析（worst-caseanalysis）：考虑在某特定长度的所有输入上的最长运行时间。平均情况分析（average-caseanalysis）：考虑在某特定长度的所有输入上的运行时间的平均值。9度量复杂性定义7.1令M是一个在所有输入上都停机的确定型图灵机。M的运行时间或者时间复杂度，是一个函数f:NN，其中N是非负整数集合，f(n)是M在所有长度为n的输入上运行时所经过的最大步数。若f(n)是M的运行时间，则称M在时间f(n)内运行，M是时间图灵机。通常使用n表示输入的长度。10渐进分析因为算法的精确运行时间通常是一个复杂的表达式，所以一般是估计它的趋势和级别。通过一种称为渐进分析(asymptoticanalysis)的方便的估计形式，可以试图了解算法在长输入上的运行时间。只考虑算法运行时间的表达式的最高项，而忽略该项的系数和其它低次项，因为在在长输入上，最高次项的影响相比其它项占据主导地位。例如，函数f(n)=6n3+2n2+20n+45称f渐进地不大于n3，表达这种关系的渐进记法或大O记法是f(n)=O(n3)。11大O和小o记法定义7.2设f和g是两个函数f，g：NR+。称f(n)=O(g(n))，若存在正整数c和n0，使得对所有n≥n0有f(n)≤cg(n)当f(n)=O(g(n))时，称g(n)是f(n)的上界，或更准确地说，g(n)是f(n)的渐近上界，以强调没有考虑常数因子。12大O和小o记法例7.3f1(n)是函数5n3+2n2+22n+6。保留最高次项5n3，并且舍去它的系数5，得到f1=O(n3)。验证该结果是否满足上面的形式定义。令c=6，n0=10，则对于所有n≥10，有5n3+2n2+22n+6≤6n3。此外，有f1=O(n4)，因为n4比n3大，它也是f1的一个渐近上界。但是f1不等于O(n2)，不论给c和n0赋什么值，始终不满足定义的要求。13大O和小o记法例7.4大O记法以一种特别的方式与对数相互影响。通常写对数时必须指明基数(或称为对数的底)，如x=log2n。这里基数2表明该等式等价于等式2x=n。logbn的值随着基数b的改变而乘以相应的常数倍，因为有恒等式logbn=log2n/log2b。所以，写f(n)=O(logn)时不必再指明基数，因为最终要忽略常数因子。14大O和小o记法令f2(n)是函数3nlog2n+5nlog2log2n+2。此时f2(n)=O(nlogn)，因为logn比loglogn更占支配位置。f(n)=O(n2)+O(n)等价于f(n)=O(n2)当O出现在指数位置，如f(n)=2O(n)，代表着2cn的一个上界。f(n)=2O(logn)，代表nc。（由n=2logn得nc=2clog2n）2O(1)代表了同样的界，因为表达式O(1)代表不超过某个固定常数的上界。15大O和小o记法我们经常导出nc的界，c是大于0的常数。这种界称为多项式界(polynamialbound)。形如的界，当是大于0的实数时，称为指数界(exponentialbound)。大O记法指一个函数渐近地不大于另一个函数。小o记法是渐进的小于另一个函数。大O记法与小o记法的区别类似于≤和＜之间的区别。2n16大O和小o记法定义7.5设f和g是两个函数f,g:NR+，如果则称f(n)=o(g(n))。换言之，f(n)=o(g(n))意味着对于任何实数c＞0，存在一个数n0，使得对所有n≥n0，f(n)＜cg(n)。()lim0()nfngn17大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))。()non18分析算法分析语言A={0k1k|k≥0}对应的图灵机算法。M1=“对于输入串w：1)扫描带子，如果在1的右边发现0，就拒绝。2)如果带上既有0也有1，就重复下一步。3)扫描带子，删除一个0和一个1。4)如果所有1都被删除以后还有0，或者所有0都被删除以后还有1，就拒绝。否则，如果在带上既没有剩下0也没有剩下1，就接受。步骤1中，机器扫描带以验证输入的形式是0*1*。执行这次扫描需要n步。读写头重新放置在带的左端另外需要n步。共需要2n步。即O(n)步。在步骤2和3中，机器反复扫描带，在每一次扫描中删除一个0和一个1。每一次扫描需要O(n)步。因为每一次扫描删除两个符号，所以最多扫描n/2次。于是步骤2和3需要的全部时间是(n/2)O(n)=O(n2)步。在步骤4中，机器扫描一次来决定是接受还是拒绝。最多需要O(n)步。所以，M1在长度为n的输入上总共耗时为O(n)+O(n2)+O(n)，或O(n2)。换言之，它的运行时间是O(n2)。19时间复杂性类定义7.7令t:NR+是一个函数。定义时间复杂性类TIME(t(n))为由O(t(n))时间的图灵机判定的所有语言的集合。语言A={0k1k|k≥0}，A∈TIME(n2)，因为M1在时间O(n2)内判定A，而TIME(n2)包括所有在时间内可判定的语言。是否存在渐近更快地判定A的机器呢？在每次扫描中删除两个0和两个1，如何？20分析M2的时间复杂性下面机器M2采用不同的方法，可以更快地判定A。A∈TIME(nlogn)。M2=“对输入串w：1)扫描带，如果1的右边发现0，就拒绝。2)只要在带上还有0和1，就重复下面的步骤。3)扫描带，检查剩余的0和1的总数是偶数还是奇数。若是奇数，就拒绝。4)再次扫描带，从第一个0开始，隔一个删除一个0；然后从第一个1开始，隔一个删除一个1.5)如果带上不再有0和1，就接受。否则拒绝。”首先注意，每一步都消耗O(n)的时间。步骤1和5执行一次，共需要O(n)时间。步骤4在每一次执行时至少删除一半的0和1，所以至多1+log2n次循环就可以把全部字符删除。于是，步骤2、3和4总共消耗时间(1+log2n)O(n)，即O(nlogn)。M2的运行时间是O(n)+O(nlogn)=O(nlogn)。A∈TIME(nlogn)。这个结果在单带图灵机上不可能进一步改进。单带图灵机在o(nlogn)时间内判定的语言都是正则语言。21分析M3的时间复杂性如果图灵机有第二条带，就可以在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剩下，就拒绝。”四个步骤中每一步需要O(n)步，所以全部的运行时间是O(n)，因而是线性的。注意，这可能是最好的运行时间，因为光是读输入就需要n步。22A的C程序A={0k1k|k=0,1,2,…}.先用用C语言写程序判断串s是否0k1kBoolM(char*s){intL=strlen(s)//扫描一遍O(n)if(L%2)!=0returnfalse;//长度不是偶数elseN=L/2;for(k=1;kN;k++)//{if(s[k]!=0)returnfalse;//O(n)if(s[k+N]!=1)returnfalse;//相当于第二条带O(n)}returntrue;}判断一个串，用O(n)时间.使用的资源:随机存取,数组，两带图灵机，23总结A的运行时间给出一个单带TMM1，能够在时间O(n2)内判定A，以及一个更快的单带TMM2，能够在时间O(nlogn)内判定A。两带TMM3能在O(n)时间内判定语言A。因此A在单带TM上的时间复杂度是O(nlogn)，在两带TM上是O(n)。注意A的复杂度与选择的计算模型有关。24复杂性理论与可计算性理论的区别在可计算性理论中，丘奇-图灵论题断言，所有合理的计算模型都是等价的，即它们所判定的语言类都是相同的。在复杂性理论中，模型的选择影响语言的时间复杂度。如在一个模型上线性时间内可判定的语言，在另一个模型上就不一定是线性时间内可判定的。在复杂性理论中，根据计算问题的时间复杂度来对问题分类。25模型间的复杂性关系定理7.8设t(n)是一个函数，t(n)≥n。则每一个时间t(n)的多带图灵机都和某一个O(t2(n))时间的单带图灵机等价。S用它的一条带表示M的所有k条带的内容。这些带连续存放，M的读写头的位置都标在恰当的方格上。01010□…Maaa□…ba□…#01010#aaa#ba#□…S26模型间的复杂性关系01010□…Maaa□…ba□…#01010#aaa#ba#□…S开始时，S让它的带形成表示M的所有带的格式，然后模拟M的步骤。为了模拟M的一步，S扫描带上的所有信息，确定在M的读写头下的符号。然后S再次扫描带，更新带内容和读写头位置。如果