计算理论导引时间复杂性

计算理论导引时间复杂性1第1页，共109页，2023年，2月20日，星期四引言Church-Turing论题：能够用总停机的Turing机计算的函数和识别的语言是可计算的（可判定的）；理论可计算计算复杂性理论研究计算模型在各种资源（主要是时间、空间等）限制下的计算能力；

实际可计算一个可以计算的问题需要多少时间和空间？64层次梵塔，1秒钟移动1000片（计算机作），要多少时间？(264-1)/1000=5.846亿年2第2页，共109页，2023年，2月20日，星期四引言复杂度和时间：每秒作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第3页，共109页，2023年，2月20日，星期四引言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两大类。4第4页，共109页，2023年，2月20日，星期四引言co-TMrecognizable（补集可识）TM-recognizableTMdecidable

PSPACEco-NPNPP5第5页，共109页，2023年，2月20日，星期四主要内容7.1度量复杂性 大O和小o记法、分析算法、模型间的复杂性关系7.2P类 多项式时间、P中的问题举例7.3NP类

NP中的问题举例、P与NP问题7.4NP完全性 多项式时间可归约性、NP完全性的定义、库克-列文定理7.5几个NP完全问题 顶点覆盖问题、哈密顿路径问题、子集和问题6第6页，共109页，2023年，2月20日，星期四度量复杂性考察下列例子： 语言A={0k1k|k

≥0}，显然A是一个可判定的语言。 考察下面判定A的单带TMM1

M1=“对于输入串w：1)扫描带子，如果在1的右边发现0，就拒绝。2)如果带上既有0也有1，就重复下一步。3)扫描带子，删除一个0和一个1。4)如果所有1都被删除以后还有0，或者所有0都被删除以后还有1，就拒绝。否则，如果在带上既没有剩下0也没有剩下1，就接受。考察判定A的图灵机M1的算法所需的时间。7第7页，共109页，2023年，2月20日，星期四度量复杂性把算法的运行时间纯粹作为表示输入字符串的长度来计算，而不考虑其它参数。最坏情况分析（worst-caseanalysis）：考虑在某特定长度的所有输入上的最长运行时间。平均情况分析（average-caseanalysis）：考虑在某特定长度的所有输入上的运行时间的平均值。8第8页，共109页，2023年，2月20日，星期四度量复杂性定义7.1令M是一个在所有输入上都停机的确定型图灵机。M的运行时间或者时间复杂度，是一个函数

f:N

N，其中N是非负整数集合，f(n)是M在所有长度为n的输入上运行时所经过的最大步数。若f(n)是M的运行时间，则称M在时间f(n)内运行，M是时间图灵机。通常使用n表示输入的长度。9第9页，共109页，2023年，2月20日，星期四渐进分析因为算法的精确运行时间通常是一个复杂的表达式，所以一般是估计它的趋势和级别。通过一种称为渐进分析

(asymptoticanalysis)的方便的估计形式，可以试图了解算法在长输入上的运行时间。只考虑算法运行时间的表达式的最高项，而忽略该项的系数和其它低次项，因为在在长输入上，最高次项的影响相比其它项占据主导地位。例如，函数f(n)=6n3+2n2+20n+45

称f渐进地不大于n3，表达这种关系的渐进记法或大O记法是f(n)=O(n3)。10第10页，共109页，2023年，2月20日，星期四大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)的渐近上界，以强调没有考虑常数因子。11第11页，共109页，2023年，2月20日，星期四大O和小o记法例7.3

f1(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赋什么值，始终不满足定义的要求。12第12页，共109页，2023年，2月20日，星期四大O和小o记法例7.4

大O记法以一种特别的方式与对数相互影响。通常写对数时必须指明基数(或称为对数的底)，如x=log2n

。这里基数2表明该等式等价于等式2x=n。logbn的值随着基数b的改变而乘以相应的常数倍，因为有恒等式logbn=log2n/log2b。所以，写f(n)=O(logn)

时不必再指明基数，因为最终要忽略常数因子。13第13页，共109页，2023年，2月20日，星期四大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)代表不超过某个固定常数的上界。14第14页，共109页，2023年，2月20日，星期四大O和小o记法我们经常导出nc

的界，c是大于0的常数。这种界称为多项式界(polynamialbound)。形如的界，当是大于0的实数时，称为指数界(exponentialbound)。大O记法指一个函数渐近地不大于另一个函数。小o记法是渐进的小于另一个函数。大O记法与小o记法的区别类似于≤和＜之间的区别。15第15页，共109页，2023年，2月20日，星期四大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)。16第16页，共109页，2023年，2月20日，星期四大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第17页，共109页，2023年，2月20日，星期四分析算法分析语言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)。18第18页，共109页，2023年，2月20日，星期四时间复杂性类定义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，如何？19第19页，共109页，2023年，2月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)时间内判定的语言都是正则语言。20第20页，共109页，2023年，2月20日，星期四分析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步。21第21页，共109页，2023年，2月20日，星期四A的C程序A={0k1k|k=0,1,2,…}.先用用C语言写程序判断串s是否0k1k

BoolM(char*s){intL=strlen(s)//扫描一遍O(n)if(L%2)!=0returnfalse;//长度不是偶数

elseN=L/2;for(k=1;k<N;k++)//{if(s[k]!=0)returnfalse;//O(n)if(s[k+N]!=1)returnfalse;//相当于第二条带O(n)}returntrue;}判断一个串，用O(n)时间.使用的资源:随机存取,数组，两带图灵机，22第22页，共109页，2023年，2月20日，星期四总结A的运行时间给出一个单带TMM1，能够在时间O(n2)内判定A，以及一个更快的单带TMM2，能够在时间O(nlogn)内判定A。两带TMM3能在O(n)时间内判定语言A。因此A在单带TM上的时间复杂度是O(nlogn)，在两带TM上是O(n)。注意A的复杂度与选择的计算模型有关。23第23页，共109页，2023年，2月20日，星期四复杂性理论与可计算性理论的区别在可计算性理论中，丘奇-图灵论题断言，所有合理的计算模型都是等价的，即它们所判定的语言类都是相同的。在复杂性理论中，模型的选择影响语言的时间复杂度。如在一个模型上线性时间内可判定的语言，在另一个模型上就不一定是线性时间内可判定的。在复杂性理论中，根据计算问题的时间复杂度来对问题分类。24第24页，共109页，2023年，2月20日，星期四模型间的复杂性关系定理7.8设t(n)是一个函数，t(n)≥n。则每一个时间t(n)的多带图灵机都和某一个O(t2(n))时间的单带图灵机等价。S用它的一条带表示M的所有k条带的内容。这些带连续存放，M的读写头的位置都标在恰当的方格上。01010□…Maaa□…ba□…#01010#aaa#ba#□…S25第25页，共109页，2023年，2月20日，星期四模型间的复杂性关系01010□…Maaa□…ba□…#01010#aaa#ba#□…S开始时，S让它的带形成表示M的所有带的格式，然后模拟M的步骤。为了模拟M的一步，S扫描带上的所有信息，确定在M的读写头下的符号。然后S再次扫描带，更新带内容和读写头位置。如果M的读写头向右移动到带上以前没有读到的位置，那么S必须增加分配给这条带的存储空间。为此，它把自己的带的一部分向右移动一格。26第26页，共109页，2023年，2月20日，星期四模型间的复杂性关系01010□…Maaa□…ba□…#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第27页，共109页，2023年，2月20日，星期四模型间的复杂性关系定义7.9设N是一个非确定型图灵机，并且是一个判定机。N的运行时间是函数f:NN

，其中

f(n)是在任何长度为n的输入上所有的计算分支中最大步数。28第28页，共109页，2023年，2月20日，星期四模型间的复杂性关系定理7.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)

。0010□…Dxx#01x□…12332312113□…输入带模拟带地址带29第29页，共109页，2023年，2月20日，星期四模型间的复杂性关系模拟过程以宽度优先法探查这棵树。换句话说，在访问深度为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))

，定理得证。

0010□…Dxx#01x□…12332312113□…输入带模拟带地址带30第30页，共109页，2023年，2月20日，星期四主要内容7.1度量复杂性 大O和小o记法、分析算法、模型间的复杂性关系7.2P类 多项式时间、P中的问题举例7.3NP类

NP中的问题举例、P与NP问题7.4NP完全性 多项式时间可归约性、NP完全性的定义、库克-列文定理7.5几个NP完全问题 顶点覆盖问题、哈密顿路径问题、子集和问题31第31页，共109页，2023年，2月20日，星期四多项式时间定理7.8和定理7.10显示出一个重要的差别。一方面，问题的时间复杂性在确定型单带和多带图灵机上最多是平方或多项式的差异；另一方面，在确定型和非确定型图灵机上，问题的时间复杂性最多是指数差异。典型的指数时间算法来源于通过搜索解空间来求解问题，这称为蛮力搜索（brute-forcesearch）。例如，分解一个数为素数因子的一种方法是搜遍所有可能的因子。搜索空间的规模是指数的，所以这种搜索需要指数时间。有时候，通过更深入地理解问题，可以避免蛮力搜索，从而可能会找到更实用的多项式时间算法。所有合理的确定型计算模型都是多项式等价的（polynomiallyequivalent），也就是说，它们中任何一个模型都可以模拟另一个，而运行时间只增长多项式倍。当称所有合理的确定型模型都多项式等价时，它足够广泛，能容纳那些和实际计算机运行时间近似的模型。例如，定理7.8表明确定型单带和多带固灵机模型是多项式等价的。32第32页，共109页，2023年，2月20日，星期四多项式时间在理论中，P类扮演核心的角色，它的重要性在于：1)对于所有与确定型单带图灵机多项式等价的计算模型来说，P是不变的。2)P大致对应于在计算机上实际可解的那一类问题。第1条表明，在数学上，P是一个稳健的类，它不受所采用的具体计算模型的影响。第2条表明，从实用的观点看，P是恰当的。当一个问题在P中的时候，就有办法在时间nk(k是常数)内求解它。至于这么长时间是否实用就依赖于k和实际的应用情况。定义7.11P是确定型单带图灵机在多项式时间内可判定的语言类。换言之，P＝TIME(nk)33第33页，共109页，2023年，2月20日，星期四P中的问题举例当给出多项式时间算法时，给出的是算法的高层描述，没有提及计算模型的特点，这样做回避了带和读写头运动的繁琐细节。分析一个算法，证明它在多项式时间内运行，需要两步：1)必须为算法在长为n的输入上运行时所需要的步骤给出多项式上界（一般用大O记法）。2)必须考虑算法描述中的每一步，保证它们都可以由合理的确定型模型在多项式时间内实现。需要注意的问题所用的编码方法。合理的方法就是允许在多项式时间内把对象编码/解码为自然的内部表示或其它合理的编码。图的一种合理编码是它的结点和边的序列。另一种是相邻矩阵，其中若从结点i到结点j

有边，则第(i,j)项为1，否则为0。34第34页，共109页，2023年，2月20日，星期四P中的问题举例--PATH有向图G包含结点s和t，如图所示。PATH问题就是要确定是否存在从s到t的有向路径。PATH={<G,s,

t>|G是具有从s到t的有向路径的有向图}st35第35页，共109页，2023年，2月20日，星期四P中的问题举例--PATH定理7.12PATH∈P

证明思路：

通过给出判定PATH的多项式时间算法来证明该定理。PATH的蛮力算法通过考察G中所有可能路径来确定是否存在从s到t的有向路径。一条可能路径就是G中长度最多为m的结点序列，m是G中的节点数。但是这些可能的路径数是

mm，这是G中结点数的指数倍。因此该蛮力算法消耗指数时间。为了获得PATH的多项式时间算法，必须设法避免蛮力搜索。一种方法是采用图搜索方法，如宽度优先搜索。连续标记G中从s出发，长度为1,2,3直到m的有向路径可达的所有节点。用多项式可以容易地来界定该策略的运行时间。36第36页，共109页，2023年，2月20日，星期四PATH∈PPATH的一个多项式时间算法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的多项式时间算法。

37第37页，共109页，2023年，2月20日，星期四P中的问题举例--RELPRIMERELPRIME代表检查两个数是否是互素问题。RELPRIME={<x,y>|x与y互素}定理7.13RELPRIME∈P

解决该问题的一种算法是搜索这两个数的所有可能的公因子。如果没有发现大于1的公因子，就接受。然而，用二进制或其它任何以k为基的记法(k≥2)表示的数字的大小是它表示长度的指数倍。因此该蛮力算法需要搜遍指数多个可能的因子，消耗指数的运行时间。改用一种古老的数值计算过程来求解该问题，称为欧几里德算法(Euclideanalgorithm)，来计算最大公因子。两个自然数的最大公因子(greatestcommondivisor)，即为gcd(x,y)，能同时整除x和y的最大整数。38第38页，共109页，2023年，2月20日，星期四RELPRIME∈P证明:欧几里德算法E如下：E=“对输入<x，y>，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>，x和y是二进制表示的自然数：

1)在<x,y>上运行E。

2)若结果为1，就接受；否则拒绝。”39第39页，共109页，2023年，2月20日，星期四P中的问题举例--上下文无关语言定理7.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的指数，所以该算法可能需要指数时间。40第40页，共109页，2023年，2月20日，星期四P中的问题举例--上下文无关语言为了获得多项式时间算法，在此介绍一种强有力的技术，称为动态规划。这种技术通过累积小的子问题的信息来解决大的问题。把子问题的解都记录下来，这样就只需对它求解一次。为此，把所有了问题编成一张表，当碰到它们时，把它们的解系统地填入表格。在本例中，考虑G的每一个变元是否产生w的每一个子串这样的子问题。算法把子问题的解填入一张n×n表格。对于i≤j，表的第(i,j)项包含产生子串wi

wi+1…wj的所有变元。i＞j的表项没有使用。算法为w的每一子串填写表项。首先为长为1的子串填写表项，然后是长为2的子串，依此类推。它利用短子串的表顶内容来辅助确定长子串的表项内容。41第41页，共109页，2023年，2月20日，星期四P中的问题举例--上下文无关语言例如，假定该算法已经确定了由哪些变元产生所有长度不超过k的子串。为了确定变元A是否产生某一长为k+1的子串，算法把该子串以k种可能方式分裂为非空的两段。对于每一种分裂方式，算法考察每一条规则ABC

，利用以前计算的表项来确定是否B产生第一段而且C产生第二段。如果B和C都产生各自的段，那么A就产生该子串，并且被加入相关联的表项。算法从长为1的串开始，对规则Ab考察表格。

42第42页，共109页，2023年，2月20日，星期四P中的问题举例--上下文无关语言证明：令G

是产生CFLL的乔姆斯基范式的CFG，假设S是起始变元。

D=“对输入w=w1…wn:1）若w=且S是一条规则，则接受。[处理w=的情况]2）Fori=1ton：[考察每一长为1的子串]3）对每一个变元A：4）检查Ab是否是一条规则，其中b=wi。5）若是，把A放入table（i，i）。6）Forl=2ton[l是子串长度]7）ForI=1ton-l+1[i是子串的起始位置]8）令j=i+l-1[j是子串的起始位置]9）Fork=i

toj-1[k是分裂位置]10）对每一条规则ABC：12）若table（i，k）包含B且table（k+1，j）包含C，则把A放入table（i，j）12）若S在table（1，n）中，则接受；否则拒绝。”43第43页，共109页，2023年，2月20日，星期四P中的问题举例--上下文无关语言现在分析D。每一步很容易在多项式时间内运行。步骤4和5最多运行nv次，其中v是G中的变元数，是与n无关的固定常数；因此这两步运行O(n)次。步骤6最多运行n次。步骤6每运行一次，步骤7最多运行n次。步骤7每运行一次，步骤8和9最多运行n次。步骤9每运行一次，步骤10运行r次，这里r是G的规则数，是另一个固定常数。所以步骤11，即该算法的内层循环，运行O(n3)次。总计D执行O(n3)步。44第44页，共109页，2023年，2月20日，星期四主要内容7.1度量复杂性 大O和小o记法、分析算法、模型间的复杂性关系7.2P类 多项式时间、P中的问题举例7.3NP类

NP中的问题举例、P与NP问题7.4NP完全性 多项式时间可归约性、NP完全性的定义、库克-列文定理7.5几个NP完全问题 顶点覆盖问题、哈密顿路径问题、子集和问题45第45页，共109页，2023年，2月20日，星期四NP类许多问题可以避免使用蛮力搜索而获得多项式时间解法。但是，在某些其它问题中，包括许多有趣而有用的问题，避免蛮力搜索的努力还没有成功，求解它们的多项式时间算法还没有找到。可能这些问题具有未知原理的多项式时间算法，但至今还没有被发现，或者它们中的某些问题就是不能在多项式时间内解决，它们可能是固有地难计算的。一个不寻常的发现是，许多问题的复杂性是联系在一起的。发现其中一个问题的多项式时间算法可以用来解决整个一类问题。46第46页，共109页，2023年，2月20日，星期四多项式可验证性许多事情,猜出困难，验证易。例如，解方程x10+2x+7=1035解方程难，验算根x=2容易。HAMPATH={＜G,s,t＞|G

是包含从s到t

的哈密顿路径的有向图}

容易获得指数时间算法，但不知是否能在多项式时间内求解。 该问题有一个特点，称为多项式可验证性。 虽然还不知道一种快速（即多项式时间）的方法来确定图中是否包含哈密顿路径，但是如果以某种方式（可能是指数时间算法）找到这样的路径，就可以相信它的存在。即：验证哈密顿路径的存在可能比确定它的存在性容易得多。COMPOSITES={x|x=pq，整数p,q＞1}

虽然不知道判断该问题的多项式时间算法，但是容易验证一个数是不是合数----只需要该数的一个因子即可。47第47页，共109页，2023年，2月20日，星期四多项式可验证性定义7.15语言A的验证机

(verifier)是一个算法V，这里

A

＝{w|对某个字符串c，V接受＜w,c＞}因为只根据w的长度来度量验证机的时间，所以多项式时间验证机在w的长度的多项式时间内运行。若语言A有一个多项式时间验证机，则称它为多项式可验证的。验证机利用额外的信息(在定义7.15中用符号c表示)来验证字符串w是A的成员。该信息称为A的成员资格证书(certificate)，或证明(proof)。注意，对于多项式验证机，证书具有多项式的长度(w的长度)，因为这是该验证机在它的时间界限内所能访问的全部信息长度。对于

HAMPATH问题，字符串<G,s,t>HAMPATH的证书就只是一条从s到t

的哈密顿路径。对于COMPOSITE

问题，合数x

的证书只是它的一个因子。48第48页，共109页，2023年，2月20日，星期四NP类定义7.16NP是具有多项式时间验证机的语言类。NP即非确定型多项式时间（nondeterministicpolynomialtime）。在NP中的问题有时被称为NP问题。49第49页，共109页，2023年，2月20日，星期四判定HAMPATH在非确定型多项式时间内判定HAMPATH问题的非确定型图灵机(NTM)：

N1=“对输入<G,s,t>，这里G

是包含结点s和t

的有向图1)写一列m个数p1,p2,…,pm

，m是G

的结点数。列中每一个数都是从1到m中非确定地挑选。2)在列中检查重复性，若发现重复，则拒绝。3)检查s

=p1和t

=pm是否都成立。若有一个不成立，则拒绝。4)对于1到m-1中每一个i，检查(pi，pi+1)是否是G

的一条边。若有一个不是，则拒绝。否则，所有检查都通过了，接受。”算法分析在步骤1中，非确定性的选择显然在多项式时间内运行。在步骤2和3中，每一步是一次简单的检查，所以合起来它们仍在多项式时间内运行。步骤4也显然在多项式时间内运行。该算法在非确定型多项式时间内运行。50第50页，共109页，2023年，2月20日，星期四NP类定理7.17一个语言在NP中，当且仅当它能被某个非确定型多项式时间图灵机判定。一个多项式时间验证机和多项式时间NTM相互转换。NTM

通过猜想证书来模拟验证机，验证机通过把接受分支作为证书来模拟NTM。51第51页，共109页，2023年，2月20日，星期四NP类从左向右的方向，设A∈NP，要证A被多项式时间NTMN判定。由NP的定义，存在A的多项式时间验证机V。假设V是一个在时间nk内运行的TM，构造N如下；

N＝“对长为n的输入w。

1)非确定地选择长为nk

的字符串c。

2)在输入<w,c>上运行V。

3)若V接受，则接受；否则拒绝。”从右向左的方向，假设A被多项式时间NTMN判定，构造多项式时间验证机V如下：

V

＝“对输入<w,c>，这里w,c是字符串：

1)在输入w上模拟N，把c的每一个符号看作是对每一步

所做的非确定性选择的描述。

2)若N的该计算分支接受，则接受；否则，拒绝。”

52第52页，共109页，2023年，2月20日，星期四NP类定义7.18NTIME(t(n))={L|L是一个被O(t(n))时间的非确定型图灵机判定的语言}推论7.19NP=∪kNTIME(nk)53第53页，共109页，2023年，2月20日，星期四NP中问题举例—CLIQUE无向图中的团(clique)是一个子图，其中每两个结点都有边相连。k团就是包含k

个的结点的团。4-cliquegraph不是5-cliqueCLIQUE={<G,k>|G是包含k团的无向图}54第54页，共109页，2023年，2月20日，星期四NP中问题举例—CLIQUE定理7.20CLIQUE属于NP。证明下面是CLIQUE的验证机V。V

＝“对输入<<G,k>,c>：

1)检查c是否是G中k个结点的集合。

2)检查G是否包含连接c中结点的所有边。

3)若两项检查都通过，则接受；否则，拒绝。”团即是证书另一种证明通过给出判定CLIQUE的图灵机来证明。N＝“对输入<G,k>，这里G是一个图：

1)非确定地选择G中k个结点的子集c。

2)检查G是否包含连接c中结点的所有边。

3)若是，则接受；否则，拒绝。”55第55页，共109页，2023年，2月20日，星期四NP中问题举例—CLIQUE如果用确定图灵机来解决。BoolDM(<G,k>){G中有m个结点，其中有k

个结点的子集有mk个，编码排序1,2,..,mkfor(i=1;i<mk

;i++)//按次序检查子集c{ok=c中两两结点之间的边在G中；

returnok;}}

说明确定机用指数时间，可以解决。但不排除某个聪明人能找到确定机P时间的方法56第56页，共109页，2023年，2月20日，星期四NP中问题举例—SUBSET-SUMSUBSET-SUM={<s,t>|s={x1,…,xk}，且存在{y1,…,yl}{x1,…,xk}使得yi=t}{x1,…,xk}和{y1,…,yl}被看做是多重集，因此允许元素重复。<{2,4,8},10>

SUBSET-SUM<{2,4,8},11>不属于

SUBSET-SUM问题的直观实例(1)不找补购物(2)装背包，又称背包问题57第57页，共109页，2023年，2月20日，星期四NP中问题举例—SUBSET-SUM定理7.21SUBSET-SUM属于NP。证明一下面是SUBSET-SUM的验证机V。V

＝“对输入<<S,t>,c>：

1)检查c是否是加起来等于

t的数的集合。

2)检查S是否包含c中的所有数。

3)若两项检查都通过，则接受；否则，拒绝。”证明二通过给出判定SUBSET-SUM的非确定性多项式时间图灵机来证明。N＝“对输入<S,t>：

1)非确定地选择S中的数的子集和c。

2)检查c是否是加起来等于

t的数的集合。

3)若检查通过，则接受；否则，拒绝。”子集即是证书58第58页，共109页，2023年，2月20日，星期四关于NP中问题的说明注意这些集合的补集，和，不是很明显地属于NP。验证某种事物不存在好像要比验证它存在更加困难。我们定义了另外一个复杂性类，称为coNP，它包括NP中的语言的补语言。还不知道coNP是否与NP不同。59第59页，共109页，2023年，2月20日，星期四P与NP问题P=成员资格可以快速地判定的语言类NP=成员资格可以快速地验证的语言类NPPP=NP这两个可能中有一个是正确的求解NP语言的已知的最好方法确定性地使用指数时间。60第60页，共109页，2023年，2月20日，星期四NP完全性在P与NP问题上的一个重大进展是在1970年代初出斯蒂芬·库克（StephenCook）和列奥尼德·列文（LeonidLevin）完成的。他们发现NP中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间算法，那么所有NP问题都是多项式时间可解的。这些问题称为NP完全的（NP-complete）。在理论方面，试图证明P不等于NP的研究者可以把注意力集中到一个NP完全问题上。在实践上，NP完全性现象可以防止为某一具体问题浪费时间，寻找本不存在的多项式时间算法。61第61页，共109页，2023年，2月20日，星期四NP完全性—可满足性问题布尔变量：取值为TRUE和FALSE，用1和0表示。布尔运算：AND、OR和NOT分别用、、表示。布尔公式：=(xy)(xy)。公式的类型：重言式、矛盾式、可满足式可满足性：对变量的某个0,1赋值使得一个公式的值等于1。SAT={<φ>|φ是可满足的布尔公式}定理7.22库克-列文（Cook-Levin）定理SAT∈P，当且仅当P=NP。该定理把SAT问题的复杂性和NP中所有问题的复杂性联系起来。62第62页，共109页，2023年，2月20日，星期四多项式时间可归约性定义7.23若存在多项式时间图灵机M，使得在任何输入w上，M停机时f(w)恰好在带上，称函数f:**为多项式时间可计算函数。定义7.24语言A称为多项式时间映射可归约到语言B，或简称多项式时间可归约到B，记为A≤pB，若存在多项式时间可计算函数

f:**，对于每一个w，有w∈Af(w)∈B，函数f称为A到B的多项式时间归约。63第63页，共109页，2023年，2月20日，星期四多项式时间可归约性定理7.25若A≤pB且B∈P，则A

∈P。设M

是判定B

的多项式时间算法，f是从A

到B的多项式时间归约。判定A

的多项式时间算法N

的描述如下：N=“对于输入w；1)计算f(w)。2)在输入f(w)上运行M

，输出M

的输出。”若w∈A

，则f(w)∈B，因为f是从A

到B的归约。于是，只要w∈A

，M就接受f(w)。另外，因为N的两个步骤都是在多项式时间内运行，所以N在多项式时间内运行。注意，步骤2在多项式时间内运行是因为两个多项式的合成还是多项式。64第64页，共109页，2023年，2月20日，星期四3SAT3SAT是可满足性问题的一种特殊情况。文字(literal)：一个布尔变量或布尔变量的非，如x

或x

。子句(clause)：是由连接起来的若干文字，如(x

yz)

。合取范式：由连接的若干个子句，亦称为cnf。3cnf：所有子句都有三个文字。3SAT={<φ>|φ是可满足的3cnf公式}65第65页，共109页，2023年，2月20日，星期四多项式时间可归约性定理7.263SAT多项式时间可归约到CLIQUE。证明思路：给出从3SAT到CLIQUE的多项式时间归约f，它把公式转化为图。在构造的图中，指定大小的团对应于公式的满足赋值。图中的结构被设计好用来模拟变量和子句的作用。66第66页，共109页，2023年，2月20日，星期四示例：从3SAT

到CLIQUEFormula(4clauses,4variables):4变量的3子句归约为团由3合取范式造对应图的方法设有k个子句（这里k=4)(1)分k

组画3k

个顶点，(2)按子句中变量标记顶点，(3)连接不在同一组中的任意两顶点(4)然后把矛盾的边去掉，如上述4步工作可在多项式时间内可完成即p—时间映射归约67第67页，共109页，2023年，2月20日，星期四示例：从3SAT

到CLIQUE均True,是个满足的指派，对应顶点成为团…有4-clique均True,是个不满足的指派…非4-clique当公式为真时，每个3-合取范式中至少一个变量为真，设红箭头所指为真68第68页，共109页，2023年，2月20日，星期四多项式时间可归约性定理7.263SAT多项式时间可归约到CLIQUE。证明：设φ是k个子句的公式，如φ=(a1∨b1∨c1)∧(a2∨b2∨c2)∧…∧(ak∨bk∨ck)归约f生成字符串＜G，k＞，其中G是如下定义的无向图。G中的结点分成k组，每组三个结点，称为三元组t1，…，tk。每个三元组对应于φ中的一个子句，三个元组中每个结点对应于相应子句的一个文字。G的每个结点用它对应的φ中的文字做标记。除两种情形以外，G的边连接了所有的节点对。同一个三元组内的节点无边相连，相反标记的两个结点无边相连，如x2和。现在说明这种构造为何能发挥作用，证明φ是可满足的当且仅当G有k团。69第69页，共109页，2023年，2月20日，星期四多项式时间可归约性假定φ有满足赋值。在满足赋值下，每个句子中至少一个文字为真。在G的每个三元组中，选择在该满足赋值下为真的文字对应的结点。如果在某一子句中不止一个文字为真，任意选择一个真文字即可。选择出来的结点将恰好形成一个k团：因为是从k个三元组中的每一个中挑选一个结点，所以选择的结点数为k。每一对选中的结点都有边相连，它们都不适合前面描述的两种例外情形。它们不可能来自同一三元组，因为从每个三元组中只选一个结点。它们也不可能有相反标记，因为它们关联的文宇在该满足赋值下都为真。所以G包含k团。假定G有k团。因为在同一个三元组中的结点都无边相连，所以团中的任何两个结点都不在同一个三元组中。因此k个三元组中的每一个都恰好包含团的一个结点。给的φ变量赋真值，使得标记团结点的每个文字都为真。这可以办到，因为具有相反标记的两个结点无边相连，所以不可能在两个团中。给变量的这种赋值满足φ，因为每个三元组包含一个团结点，所以每个子句包含一个赋值为TRUE的文字。φ可满足。70第70页，共109页，2023年，2月20日，星期四NP完全性定义从多项式时间可归约性的定义直接可得。定义7.27如果语言B满足下面两个条件，就称为NP完全的：1）B属于NP，并且2）NP中的每个A都多项式时间可归约到B。定理7.28若上述的B是NP完全的，且B∈P，则P=NP。71第71页，共109页，2023年，2月20日，星期四NP完全性定义已知C属于NP，必须证明NP中每一个A都多项式时间可归约到C。因为B是NP完全的，所以NP中的每个语言都多项式时间可归约到B，而B又多项式时间可归约到C。多项式时间归约是可以复合的，即若A多项式时间可归约C，且B多项式时间可归约到C

，则A多项式时间可归约到C

。因此NP中的每个语言都多项式时间可归约到C

。定理7.29若上述的B是NP完全的，且B≤pC，C属于NP，则C是NP完全的。72第72页，共109页，2023年，2月20日，星期四库克-列文定理给NP中的每一个语言A构造一个到SAT的多项式时间归约，A的归约在字符串w上产生布尔公式φ，用它模拟A的NP机器在输入w上的运行。首先证明SAT属于NP。非确定型多项式时间机器可以猜测给定的公式φ的一个赋值，当赋值满足φ时接受。下面，从NP中任取一个语言A，证明A多项式可归约到SAT。设N是在时间nk内判定A的非确定型图灵机，k是某个常数。（实际假定N在时间nk-3）在w上，N对应的画面是一张nk×

nk的表格，其中行代表N在输入w上的一个计算分支的格局。定理7.30SAT是NP完全的。73第73页，共109页，2023年，2月20日，星期四库克-列文定理#q0w1w2…wn□…□#######nknk起始格局第二个格局第nk个格局窗口74第74页，共109页，2023年，2月20日，星期四库克-列文定理现在描述从A到SAT的多项式时间归约f。在输入w上，该归约产生一个公式φ。从描述φ

的变量开始，设Q和是N的状态集和带字母表，令C=Q∪∪{#}。对于每个介于1到nk之间的i和j以及C中的每个s，有一个变量xi,j,s。若xi,j,s取值1，则意味着cell[i,j]包含s。设计φ，使得变量的一个满足赋值确实对应N在w上的一个接受画面。公式φ是四部分的AND运算：

φcell

∧φstart

∧φmove

∧φaccept75第75页，共109页，2023年，2月20日，星期四库克-列文定理φstart=φaccept=

φmove保证，表的每一行都对应于上一行的格局、按照N的规则、合法转移得到的格局。它通过每一个2×3窗口单元都是合法的来保证这一点。如果一个2×3的窗口不违反由N的转移函数指定的动作，则称该窗口是合法的。换言之，如果它可以出现在从一个格局正确地转移到另一个格局的过程中，该窗口就称为合法的。76第76页，共109页，2023年，2月20日，星期四库克-列文定理例，设a,b,c是带字母表的成员，q1和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#baabaabq2bbbcbbaq1baaq2aaq1aab77第77页，共109页，2023年，2月20日，星期四库克-列文定理该机器的不合法窗口：abaaaabq1bq2bq2aq1bq1aa78第78页，共109页，2023年，2月20日，星期四库克-列文定理断言7.31如果表的顶行是起始格局，表中的每一个窗口都是合法的，那么表的每一行都是从上一行合法转移得到的格局。考虑表的任意两个相邻格局，称为上格局和下格局。在上格局中，每一个不与状态符号相邻的而且不含边界符号的单元，都是某个窗口顶行的中间单元且窗口顶行不含状态。因此该符号必定保持不变，出现在窗口的底行中间，即出现在底行格局的同一位置。窗口顶行的中间单元包含状态符号，这就使相应的三个位置按照转移函数的要求一致更新。因此，如果上格局是合法格局，那么下格局也是，并且下格局是根据N的规则从上格局转移得到。注意，这个证明显然易懂，但它的关键依赖于选择了大小为2×3的窗口。79第79页，共109页，2023年，2月20日，星期四库克-列文定理考虑表的任意两个相邻格局，称为上格局和下格局。断言7.31如果表的顶行是起始格局，表中的每一个窗口都是合法的，那么表的每一行都是从上一行合法转移得到的格局。分析归约的复杂性画面是nk×nk表格，包含n2k个单元，每个单元有与它相关联的l个变量，l是C中的符号的数目。所以变量总数是O(n2k)。φCELL的长度为O(n2k)。φSTART的长度为O(nk)。φACCEPT的长度为O(n2k)。φMOVE的长度为O(n2k)。80第80页，共109页，2023年，2月20日，星期四库克-列文定理推论7.323SAT是NP完全的。81第81页，共109页，2023年，2月20日，星期四主要内容7.1度量复杂性 大O和小o记法、分析算法、模型间的复杂性关系7.2P类 多项式时间、P中的问题举例7.3NP类

NP中的问题举例、P与NP问题7.4NP完全性 多项式时间可归约性、NP完全性的定义、库克-列文定理7.5几个NP完全问题 顶点覆盖问题、哈密顿路径问题、子集和问题82第82页，共109页，2023年，2月20日，星期四几个NP完全问题推论7.33CLIQUE是NP完全的。证明某语言是NP完全的，一般的策略是给出从3SAT到该语言的多项式时间归约。在构造3SAT到一个语言的多项式时间归约时，要