计算理论导引_7_时间复杂性ppt课件

1、朴秀峰xfpiao126计算实际第7章 时间复杂性引言Church-Turing论题：可以用总停机的Turing机计算的函数和识别的言语是可计算的可断定的；实际可计算计算复杂性实际研讨计算模型在各种资源主要是时间、空间等限制下的计算才干； 实践可计算一个可以计算的问题 需求多少时间和空间？64层次梵塔，1秒钟挪动1000片计算机作，要多少时间？( 264-1) / 1000=5.846 亿年引言复杂度和时间 ：每秒作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-

2、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世纪引言Complexity：Hamilton回路问题HC：任给一个无向图G，问G中有Hamilton回路吗？Hamilton回路是指经过每一个顶点且每一个顶点只经过一次的回路。设G有n个顶点，由于回路没有始点和终点，可以恣意定一个顶点作为陈列的第一个顶点，共有n-1！个陈列。当n=25

3、时，24！=6.2*1023.假设用一台超级计算机计算，每秒可以检查1亿个陈列。每年有3.15*107秒，不停地任务，每年可以检查3.15*1015个陈列。检查完一切的陈列需求1.97*108年，即1亿9千7百年！计算复杂性实际就是要研讨计算模型在各种资源限制下的计算才干。将问题划分成Hard and Easy 两大类。引言co-TM recognizable补集可识TM-recognizable TM decidable PSPACE co-NPNP P主要内容7.1 度量复杂性大 O 和小 o 记法、分析算法、模型间的复杂性关系7.2 P类多项式时间、P 中的问题举例7.3 NP类NP中的

4、问题举例、P 与 NP 问题7.4 NP完全性多项式时间可归约性、NP 完全性的定义、库克-列文定理7.5 几个NP完全问题顶点覆盖问题、哈密顿途径问题、子集和问题度量复杂性调查以下例子：言语 A = 0k1k | k 0 ，显然 A 是一个可断定的言语。调查下面断定A的单带 TM M1M1=“对于输入串 w：1) 扫描带子，假设在 1 的右边发现 0，就回绝。2) 假设带上既有 0 也有 1，就反复下一步。3) 扫描带子，删除一个 0 和一个 1。4) 假设一切 1 都被删除以后还有 0，或者一切 0 都被删除以后还有 1，就回绝。否那么，假设在带上既没有剩下0也没有剩下 1，就接受。调查断

5、定 A 的图灵机 M1 的算法所需的时间。度量复杂性把算法的运转时间纯粹作为表示输入字符串的长度来计算，而不思索其它参数。最坏情况分析worst-case analysis：思索在某特定长度的一切输入上的最长运转时间。平均情况分析average-case analysis：思索在某特定长度的一切输入上的运转时间的平均值。度量复杂性定义7.1令 M 是一个在一切输入上都停机确实定型图灵机。M 的运转时间或者时间复杂度，是一个函数 f : N N，其中 N 是非负整数集合， f(n) 是 M 在一切长度为 n 的输入上运转时所经过的最大步数。假设 f(n) 是 M 的运转时间，那么称 M 在时间

6、f(n) 内运转，M 是时间图灵机。通常运用 n 表示输入的长度。渐进分析由于算法的准确运转时间通常是一个复杂的表达式，所以普通是估计它的趋势和级别。经过一种称为渐进分析 (asymptotic analysis) 的方便的估计方式，可以试图了解算法在长输入上的运转时间。只思索算法运转时间的表达式的最高项，而忽略该项的系数和其它低次项，由于在在长输入上，最高次项的影响相比其它项占据主导位置。例如，函数 f (n) = 6n3+2n2+20n+45称 f 渐进地不大于 n3，表达这种关系的渐进记法或大 O 记法是 f (n) = O(n3)。 大 O 和小 o记法定义7.2设 f 和 g 是两个

7、函数 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)的渐近上界，以强调没有思索常数因子。大 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 的

8、一个渐近上界。但是 f1 不等于 O(n2)，不论给 c 和 n0 赋什么值，一直不满足定义的要求。大 O 和小 o 记法例7.4 大O记法以一种特别的方式与对数相互影响。通常写对数时必需指明基数(或称为对数的底)，如 x=log2n 。这里基数 2 阐明该等式等价于等式 2x=n。logbn 的值随着基数 b 的改动而乘以相应的常数倍，由于有恒等式 logbn = log2n / log2b。所以，写 f(n) = O(logn) 时不用再指明基数，由于最终要忽略常数因子。大 O 和小 o 记法令 f2(n) 是函数 3nlog2n+5nlog2log2n+2。 此时 f2(n) =O(nl

9、ogn)，由于 logn 比 log logn更占支配位置。f(n) =O(n2)+ O(n) 等价于 f(n) =O(n2)当 O 出如今指数位置，如 f(n) =2O(n)，代表着 2cn 的一个上界。f(n) =2O(logn)，代表 nc。由 n = 2log n 得 nc = 2c log 2n2O(1) 代表了同样的界，由于表达式 O(1) 代表不超越某个固定常数的上界。大O 和小o 记法我们经常导出 nc 的界，c 是大于 0 的常数。这种界称为多项式界 (polynamial bound)。形如 的界，当 是大于 0的实数时，称为指数界(exponential bound)。大

10、 O 记法指一个函数渐近地不大于另一个函数。小 o 记法是渐进的小于另一个函数。大O记法与小o记法的区别类似于和之间的区别。大O 和小o 记法定义7.5设 f 和 g 是两个函数 f , g : N R+，假设那么称 f (n) = o(g(n)。换言之，f (n) = o(g(n) 意味着对于任何实数 c0，存在一个数 n0，使得对一切 nn0，f (n)cg(n)。大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) 不会

11、等于o(f(n) 。分析算法分析言语 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和一个

12、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)。时间复杂性类定义7.7令 t : N R+ 是一个函数。定义时间复杂性类TIME(t(n) 为由 O(t(n) 时间的图灵机断定的一切言语的集合。言语 A = 0k1k | k0 ，ATIME(n2)，由于 M1 在时间 O(n2) 内断定 A，而 TIME(n2) 包括

13、一切在时间内可断定的言语。能否存在渐近更快地断定 A 的机器呢？在每次扫描中删除两个 0 和两个 1，如何？分析 M2 的时间复杂性下面机器 M2 采用不同的方法，可以更快地断定 A。ATIME(nlogn)。M2=“对输入串 w：1) 扫描带，假设 1 的右边发现 0，就回绝。2) 只需在带上还有 0 和 1，就反复下面的步骤。3) 扫描带，检查剩余的 0 和 1 的总数是偶数还是奇数。 假设是奇数，就回绝。4) 再次扫描带，从第一个 0 开场，隔一个删除一个 0； 然后从第一个 1 开场，隔一个删除一个 1.5) 假设带上不再有 0 和 1，就接受。否那么回绝。首先留意，每一步都耗费 O(

14、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)。 ATIME(nlogn)。这个结果在单带图灵机上不能够进一步改良。单带图灵机在o(nlogn)时间内断定的言语都是正那么言语。分析M3的时间复杂性假设图灵机有第二条带，就可以在O(n)时间也称为线性时间内断定言语A。下面的两带图灵机TM M3在线性时间内断定A。M3 = “ 对于输入串 w：1) 扫描带

15、，假设 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步。A 的 C 程序A = 0k1k | k=0,1,2, . 先用用C言语写程序判别串 s 能否 0k1k Bool M(char *

16、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)时间. 运用的资源:随机存取,数组，两带图灵机，总结 A 的运转时间给出一个单带 TM M1，可以在时间 O(n2)内断定A，以及一个更快的单带 TM M2，可以在时间 O(nlogn)内断定A。两带 TM M3

17、能在 O(n) 时间内断定言语A。因此 A 在单带 TM 上的时间复杂度是 O(nlogn)，在两带TM 上是 O(n)。留意 A 的复杂度与选择的计算模型有关。复杂性实际与可计算性实际的区别在可计算性实际中，丘奇-图灵论题断言，一切合理的计算模型都是等价的，即它们所断定的言语类都是一样的。在复杂性实际中，模型的选择影响言语的时间复杂度。如在一个模型上线性时间内可断定的言语，在另一个模型上就不一定是线性时间内可断定的。在复杂性实际中，根据计算问题的时间复杂度来对问题分类。模型间的复杂性关系定理7.8设 t(n) 是一个函数， t(n)n。那么每一个时间 t(n)的多带图灵机都和某一个 O(t2

18、(n) 时间的单带图灵机等价。S 用它的一条带表示 M 的一切k条带的内容。这些带延续存放， M 的读写头的位置都标在恰当的方格上。01010Maaaba#01010#aaa#ba#S模型间的复杂性关系01010Maaaba#01010#aaa#ba#S开场时， S 让它的带构成表示 M 的一切带的格式，然后模拟 M 的步骤。为了模拟 M 的一步， S 扫描带上的一切信息，确定在 M 的读写头下的符号。然后 S 再次扫描带，更新带内容和读写头位置。假设 M 的读写头向右挪动到带上以前没有读到的位置，那么 S 必需添加分配给这条带的存储空间。为此，它把本人的带的一部分向右挪动一格。模型间的复杂性

19、关系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)，证毕。模型间的复杂

20、性关系定义7.9设 N 是一个非确定型图灵机，并且是一个断定机。N 的运转时间是函数 f : NN ，其中 f(n) 是在任何长度为 n 的输入上一切的计算分支中最大步数。模型间的复杂性关系定理7.10设 t(n) 是一个函数， t(n)n 。那么每一个 t(n) 时间的非确定型单带图灵机都与某一 2O(t(n) 时间确实定型图灵机等价。设N是一个在时间t(n)内运转的非确定型TM ，构造确定型TM D，D经过搜索N 的非确定型计算树来模拟N。 在长度为n的输入上，N的非确定型计算树的每一个分支的长度最多是t(n) ，树的每一个结点最多有b个子女，其中b是N 的转移函数所决议的合法选择的最大值

21、。因此树叶的总数最多是bt(n) 。0010Dxx#01x12332312113输入带模拟带地址带模型间的复杂性关系模拟过程以宽度优先法探查这棵树。换句话说，在访问深度为d+1的结点之前，先访问一切深度为d 的结点。树中结点的总数小于最大叶数的两倍，因此用O(bt(n)作它的上界。从根出发下行到一个结点的时间是O(t(n) 。因此，D的运转时间是O(t(n) bt(n) = 2O(t(n) 。TM D有三条带。把它转变为单带TM，最多使运转时间乘方。这样，单带模拟机的运转时间是(2O(t(n)2 = 2O(2t(n) = 2O(t(n) ，定理得证。 0010Dxx#01x1233231211

22、3输入带模拟带地址带主要内容7.1 度量复杂性大 O 和小 o 记法、分析算法、模型间的复杂性关系7.2 P类多项式时间、P 中的问题举例7.3 NP类NP中的问题举例、P 与 NP 问题7.4 NP完全性多项式时间可归约性、NP 完全性的定义、库克-列文定理7.5 几个NP完全问题顶点覆盖问题、哈密顿途径问题、子集和问题多项式时间定理7.8和定理7.10显示出一个重要的差别。一方面，问题的时间复杂性在确定型单带和多带图灵机上最多是平方或多项式的差别；另一方面，在确定型和非确定型图灵机上，问题的时间复杂性最多是指数差别。典型的指数时间算法来源于经过搜索解空间来求解问题，这称为蛮力搜索brute

23、-force search。例如，分解一个数为素数因子的一种方法是搜遍一切能够的因子。搜索空间的规模是指数的，所以这种搜索需求指数时间。有时候，经过更深化地了解问题，可以防止蛮力搜索，从而能够会找到更适用的多项式时间算法。一切合理确实定型计算模型都是多项式等价的polynomially equivalent，也就是说，它们中任何一个模型都可以模拟另一个，而运转时间只增长多项式倍。当称一切合理确实定型模型都多项式等价时，它足够广泛，能包容那些和实践计算机运转时间近似的模型。例如，定理7.8阐明确定型单带和多带固灵机模型是多项式等价的。多项式时间在实际中，P类扮演中心的角色，它的重要性在于：1)对

24、于一切与确定型单带图灵机多项式等价的计算模型来说，P是不变的。2)P大致对应于在计算机上实践可解的那一类问题。第1条阐明，在数学上，P是一个稳健的类，它不受所采用的详细计算模型的影响。第2条阐明，从适用的观念看，P是恰当的。当一个问题在P中的时候，就有方法在时间nk(k是常数)内求解它。至于这么长时间能否适用就依赖于k和实践的运用情况。定义7.11P 是确定型单带图灵机在多项式时间内可断定的言语类。换言之， P TIME(nk)P中的问题举例当给出多项式时间算法时，给出的是算法的高层描画，没有提及计算模型的特点，这样做逃避了带和读写头运动的繁琐细节。分析一个算法，证明它在多项式时间内运转，需求

25、两步：1) 必需为算法在长为 n 的输入上运转时所需求的步骤给出多项式上界普通用大 O 记法。2) 必需思索算法描画中的每一步，保证它们都可以由合理确实定型模型在多项式时间内实现。需求留意的问题所用的编码方法。合理的方法就是允许在多项式时间内把对象编码/解码为自然的内部表示或其它合理的编码。图的一种合理编码是它的结点和边的序列。另一种是相邻矩阵，其中假设从结点 i 到结点 j 有边，那么第 ( i , j ) 项为 1，否那么为 0。P中的问题举例-PATH有向图 G 包含结点 s 和 t ，如下图。PATH 问题就是要确定能否存在从 s 到 t 的有向途径。PATH = | G 是具有从 s

26、 到 t 的有向途径的有向图stP中的问题举例-PATH定理7.12PATHP 证明思绪： 经过给出断定PATH的多项式时间算法来证明该定理。PATH 的蛮力算法经过调查 G 中一切能够途径来确定能否存在从 s 到 t 的有向途径。一条能够途径就是 G 中长度最多为 m 的结点序列， m 是 G 中的节点数。但是这些能够的途径数是 mm，这是 G 中结点数的指数倍。因此该蛮力算法耗费指数时间。为了获得 PATH 的多项式时间算法，必需设法防止蛮力搜索。一种方法是采用图搜索方法，如宽度优先搜索。延续标志 G 中从 s 出发，长度为 1, 2, 3 直到 m 的有向途径可达的一切节点。用多项式可以

27、容易地来界定该战略的运转时间。PATHPPATH 的一个多项式时间算法 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 很容易

28、用任问合理确实定型模型在多项式时间内实现。步骤 3 需求扫描输入，检查某些结点能否被标志，这也容易在多项式时间内实现。所以 M 是 PATH 的多项式时间算法。 P中的问题举例- RELPRIMERELPRIME 代表检查两个数能否是互素问题。RELPRIME = | x 与 y 互素定理7.13RELPRIMEP 处理该问题的一种算法是搜索这两个数的一切能够的公因子。假设没有发现大于 1 的公因子，就接受。然而，用二进制或其它任何以 k 为基的记法(k2) 表示的数字的大小是它表示长度的指数倍。因此该蛮力算法需求搜遍指数多个能够的因子，耗费指数的运转时间。改用一种古老的数值计算过程来求解该问

29、题，称为欧几里德算法(Euclidean algorithm)，来计算最大公因子。两个自然数的最大公因子(greatest common divisor)，即为gcd(x, y)，能同时整除 x 和 y 的最大整数。RELPRIMEP 证明: 欧几里德算法 E 如下：E=“对输入，x 和 y 是二进制表示的自然数：1) 反复下面的操作，直到 y=0.2) 赋值 x x mod y3) 交换 x 和 y4) 输出 x。显然，假设 E 在多项式时间内运转且正确，那么 R 也在多项式时间内运转且正确。所以只需分析 E 的时间和正确性。步骤2的每一次执行(除了第一次有能够例外)，都把 x 的值至少减少

30、一半。 每一次执行步骤 3都使 x 和 y 的值相互交换，所以每两次循环就使得 x 和 y原先的值至少减少一半。于是步骤 2 和 3 执行的最大次数是 2log2x 和 2log2y 中较小的那一个。这两个对数与表示的长度成正比，步骤的执行次数是 O(n)。 E 的每一步仅耗费多项式时间，所以整个运转时间是多项式的。算法 R 以 E 为子程序求解 RELPRIMER=“对输入 ，x 和 y 是二进制表示的自然数： 1) 在 上运转E。 2) 假设结果为 1，就接受；否那么回绝。P中的问题举例-上下文无关言语定理7.14每一个上下文无关言语都是 P 的成员。证明思绪： 定理4.8 证明了每一个

31、CFL 是可断定的，并且为每一个 CFL给出了断定算法。假设那个算法在多项式时间内运转，那么本定理作为推论就必然成立。回想那个算法，看它运转得能否够快。 令 L 是一个由 CFG G 产生的 CFG，G 是乔姆斯基范式。由问题2.26知：因 G 是乔姆斯基范式，任何得到字符串 w 的推导都有 2n-1步，n 是 w 的长度。当给 L 的断定机输入长为 n 的字符串时，它经过试遍一切能够的 2n-1 步推导来断定 L。假设其中有一个得到 w 的推导，该断定机就接受；否那么，就回绝。 分析一下该算法可知，它不能在多项式时间内运转。 k 步推导的数量能够到达 k 的指数，所以该算法能够需求指数时间。

32、P中的问题举例-上下文无关言语为了获得多项式时间算法，在此引见一种强有力的技术，称为动态规划。这种技术经过累积小的子问题的信息来处理大的问题。把子问题的解都记录下来，这样就只需对它求解一次。为此，把一切了问题编成一张表，当碰到它们时，把它们的解系统地填入表格。在本例中，思索 G 的每一个变元能否产生 w 的每一个子串这样的子问题。算法把子问题的解填入一张 nn表格。对于 ij，表的第 (i, j) 项包含产生子串 wi wi+1 wj 的一切变元。 ij 的表项没有运用。算法为 w 的每一子串填写表项。首先为长为 1 的子串填写表项，然后是长为 2 的子串，依此类推。它利用短子串的表顶内容来辅

33、助确定长子串的表项内容。P中的问题举例-上下文无关言语 例如，假定该算法曾经确定了由哪些变元产生一切长度不超越 k 的子串。为了确定变元 A 能否产生某一长为 k+1 的子串，算法把该子串以k种能够方式分裂为非空的两段。对于每一种分裂方式，算法调查每一条规那么 A BC ，利用以前计算的表项来确定能否 B 产生第一段而且 C 产生第二段。假设 B 和 C 都产生各自的段，那么 A 就产生该子串，并且被参与相关联的表项。算法从长为 1 的串开场，对规那么 A b 调查表格。 P中的问题举例-上下文无关言语证明：令G 是产生CFL L的乔姆斯基范式的CFG，假设S是起始变元。 D=“对输入w =w

34、1wn:1假设w = 且S 是一条规那么，那么接受。 处置w = 的情况2For i = 1 to n： 调查每一长为1的子串3 对每一个变元 A：4 检查A b能否是一条规那么，其中b = wi。5 假设是，把A放入tablei，i。6For l = 2 to n l是子串长度7 For I = 1 to n-l+1 i是子串的起始位置8 令j = i +l-1 j是子串的起始位置9 For k =i to j-1 k是分裂位置10 对每一条规那么 A BC：12 假设tablei，k包含B且tablek+1，j包含C，那么把 A 放入tablei，j12假设S在table1，n中，那么接受

35、；否那么回绝。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)步。主要内容7.1 度量复杂性大 O 和小 o 记法、分析算法、模型间的复杂性关系7.2 P类多项式时间、P 中的问题举例7.3 NP类NP中的问题举例、P 与

36、NP 问题7.4 NP完全性多项式时间可归约性、NP 完全性的定义、库克-列文定理7.5 几个NP完全问题顶点覆盖问题、哈密顿途径问题、子集和问题NP 类许多问题可以防止运用蛮力搜索而获得多项式时间解法。但是，在某些其它问题中，包括许多有趣而有用的问题，防止蛮力搜索的努力还没有胜利，求解它们的多项式时间算法还没有找到。能够这些问题具有未知原理的多项式时间算法，但至今还没有被发现，或者它们中的某些问题就是不能在多项式时间内处理，它们能够是固有地难计算的。一个不寻常的发现是，许多问题的复杂性是联络在一同的。发现其中一个问题的多项式时间算法可以用来处理整个一类问题。多项式可验证性许多事情, 猜出困难

37、，验证易。例如，解方程 x10+2x+7=1035解方程难，验算根x=2容易。HAMPATH = G,s,t | G 是包含从 s 到 t 的哈密顿途径的有向图容易获得指数时间算法，但不知能否能在多项式时间内求解。该问题有一个特点，称为多项式可验证性。虽然还不知道一种快速即多项式时间的方法来确定图中能否包含哈密顿途径，但是假设以某种方式能够是指数时间算法找到这样的途径，就可以置信它的存在。即：验证哈密顿途径的存在能够比确定它的存在性容易得多。COMPOSITES = x | x = pq，整数 p,q1虽然不知道判别该问题的多项式时间算法，但是容易验证一个数是不是合数-只需求该数的一个因子即可

38、。多项式可验证性定义7.15言语 A 的验证机 (verifier) 是一个算法 V，这里 A w | 对某个字符串 c，V 接受w, c由于只根据 w 的长度来度量验证机的时间，所以多项式时间验证机在 w 的长度的多项式时间内运转。假设言语 A 有一个多项式时间验证机，那么称它为多项式可验证的。验证机利用额外的信息(在定义7.15中用符号 c 表示)来验证字符串 w 是A 的成员。该信息称为 A 的成员资历证书(certificate)，或证明(proof)。留意，对于多项式验证机，证书具有多项式的长度 ( w 的长度)，由于这是该验证机在它的时间界限内所能访问的全部信息长度。对于 HAMP

39、ATH 问题，字符串 HAMPATH 的证书就只是一条从s 到 t 的哈密顿途径。对于 COMPOSITE 问题，合数 x 的证书只是它的一个因子。NP类定义7.16NP 是具有多项式时间验证机的言语类。NP 即非确定型多项式时间nondeterministic polynomial time。在 NP 中的问题有时被称为 NP 问题。断定 HAMPATH在非确定型多项式时间内断定 HAMPATH 问题的非确定型图灵机 (NTM)：N1 = “对输入，这里 G 是包含结点 s 和 t 的有向图1) 写一列 m 个数 p1 , p2 , , pm ，m 是 G 的结点数。列中每一个数都是从 1

40、到 m 中非确定地挑选。2) 在列中检查反复性，假设发现反复，那么回绝。3) 检查 s = p1 和 t = pm 能否都成立。假设有一个不成立，那么回绝。4) 对于 1 到 m-1 中每一个 i，检查 ( pi，pi+1) 能否是 G 的一条边。假设有一个不是，那么回绝。否那么，一切检查都经过了，接受。算法分析在步骤 1 中，非确定性的选择显然在多项式时间内运转。在步骤 2 和 3 中，每一步是一次简单的检查，所以合起来它们仍在多项式时间内运转。步骤4 也显然在多项式时间内运转。该算法在非确定型多项式时间内运转。NP类定理7.17一个言语在 NP 中，当且仅当它能被某个非确定型多项式时间图灵

41、机断定。一个多项式时间验证机和多项式时间 NTM 相互转换。NTM 经过猜测证书来模拟验证机，验证机经过把接受分支作为证书来模拟 NTM。NP类从左向右的方向，设 A NP，要证 A 被多项式时间 NTM N 断定。由 NP 的定义，存在 A 的多项式时间验证机 V。假设 V 是一个在时间 nk 内运转的 TM，构造 N 如下； N“对长为 n 的输入 w。 1) 非确定地选择长为 nk 的字符串 c。 2) 在输入 上运转 V。 3) 假设 V 接受，那么接受；否那么回绝。从右向左的方向，假设 A 被多项式时间 NTM N 断定，构造多项式时间验证机 V 如下： V “对输入，这里 w, c

42、 是字符串： 1) 在输入 w 上模拟 N，把 c 的每一个符号看作是对每一步 所做的非确定性选择的描画。 2) 假设 N 的该计算分支接受，那么接受；否那么，回绝。 NP类定义7.18NTIME(t(n) = L | L是一个被O (t(n)时间的非确定型图灵机断定的言语推论7.19NP = kNTIME(nk)NP中问题举例CLIQUE无向图中的团 (clique)是一个子图，其中每两个结点都有边相连。k团 就是包含 k 个的结点的团。4-cliquegraph不是 5-cliqueCLIQUE = | G 是包含 k 团的无向图NP中问题举例CLIQUE定理7.20CLIQUE 属于 N

43、P。证明 下面是 CLIQUE 的验证机 V。V “对输入, c： 1) 检查 c 能否是 G 中 k 个结点的集合。 2) 检查 G 能否包含衔接 c 中结点的一切边。 3) 假设两项检查都经过，那么接受；否那么，回绝。团即是证书另一种证明 经过给出断定 CLIQUE 的图灵机来证明。N“对输入，这里 G 是一个图： 1) 非确定地选择 G 中 k 个结点的子集 c。 2) 检查 G 能否包含衔接 c 中结点的一切边。 3) 假设是，那么接受；否那么，回绝。NP中问题举例CLIQUE假设用确定图灵机来处理。Bool DM( ) G 中有 m 个结点，其中有 k 个结点的子集有mk个， 编码排

44、序 1, 2, . , mk for ( i=1; i mk ; i+) /按次序检查子集 c ok= c中两两结点之间的边在 G 中； return ok ; 阐明 确定机用 指数时间，可以处理。 但不排除 某个聪明人能找到 确定机 P 时间的方法 NP中问题举例SUBSET-SUMSUBSET-SUM = | s = x1 , , xk，且存在 y1 , yl x1 , ,xk 使得 yi = t x1 , xk 和 y1 , yl 被看做是多重集，因此允许元素反复。 SUBSET-SUM 不属于 SUBSET-SUM问题的直观实例 (1)不找补 购物 (2) 装背包，又称背包问题NP中问

45、题举例SUBSET-SUM定理7.21SUBSET-SUM 属于 NP。证明一 下面是 SUBSET-SUM 的验证机V。V “对输入, c： 1)检查 c 能否是加起来等于 t 的数的集合。 2)检查 S 能否包含 c 中的一切数。 3)假设两项检查都经过，那么接受；否那么，回绝。证明二 经过给出断定SUBSET-SUM的非确定性多项式时间图灵机来证明。N“对输入： 1)非确定地选择 S 中的数的子集和 c。 2)检查 c 能否是加起来等于 t 的数的集合。 3)假设检查经过，那么接受；否那么，回绝。子集即是证书关于 NP 中问题的阐明 留意这些集合的补集， 和 ，不是很明显地属于NP。验证

46、某种事物不存在好似要比验证它存在更加困难。我们定义了另外一个复杂性类，称为coNP，它包括 NP 中的言语的补言语。还不知道 coNP 能否与 NP 不同。P 与 NP 问题P=成员资历可以快速地断定的言语类NP=成员资历可以快速地验证的言语类NPPP=NP这两个能够中有一个是正确的求解NP言语的知的最好方法确定性地运用指数时间。NP完全性 在 P 与 NP 问题上的一个艰苦进展是在 1970 年代初出斯蒂芬库克Stephen Cook和列奥尼德列文Leonid Levin完成的。他们发现 NP 中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个假设存在多项式时间算法，那么一切 N

47、P 问题都是多项式时间可解的。这些问题称为 NP完全的NP-complete。在实际方面，试图证明 P 不等于 NP 的研讨者可以把留意力集中到一个 NP 完全问题上。在实际上，NP 完全性景象可以防止为某一详细问题浪费时间，寻觅本不存在的多项式时间算法。NP完全性可满足性问题布尔变量：取值为 TRUE 和 FALSE，用 1 和 0 表示。布尔运算： AND、OR 和 NOT 分别用、表示。布尔公式： = (x y) (x y)。公式的类型：重言式、矛盾式、可满足式可满足性：对变量的某个 0,1 赋值使得一个公式的值等于1。SAT = |是可满足的布尔公式定理7.22库克-列文Cook-Le

48、vin定理SATP，当且仅当 P=NP。该定理把 SAT 问题的复杂性和 NP 中一切问题的复杂性联络起来。多项式时间可归约性定义7.23假设存在多项式时间图灵机 M，使得在任何输入w上，M 停机时 f (w) 恰好在带上，称函数 f : * 为多项式时间可计算函数。定义7.24言语 A 称为多项式时间映射可归约到言语 B，或简称多项式时间可归约到 B，记为 ApB，假设存在多项式时间可计算函数 f : *，对于每一个 w，有 wA f(w)B，函数 f 称为 A 到 B 的多项式时间归约。多项式时间可归约性定理7.25假设 ApB 且 BP，那么 A P。设 M 是断定B 的多项式时间算法，

49、 f 是从 A 到 B 的多项式时间归约。断定 A 的多项式时间算法 N 的描画如下：N = “对于输入w ；1) 计算 f (w) 。2) 在输入 f (w) 上运转M ，输出M 的输出。假设wA ，那么 f(w)B，由于 f 是从 A 到 B的归约。于是，只需wA ， M 就接受 f (w)。另外，由于N 的两个步骤都是在多项式时间内运转，所以N 在多项式时间内运转。留意，步骤 2 在多项式时间内运转是由于两个多项式的合成还是多项式。3SAT3SAT是可满足性问题的一种特殊情况。文字(literal)：一个布尔变量或布尔变量的非，如 x 或 x 。子句(clause)：是由衔接起来的假设干

50、文字，如(x y z) 。合取范式：由衔接的假设干个子句，亦称为 cnf 。3cnf：一切子句都有三个文字。3SAT = |是可满足的 3cnf 公式多项式时间可归约性定理7.263SAT 多项式时间可归约到 CLIQUE 。证明思绪：给出从 3SAT 到 CLIQUE 的多项式时间归约 f，它把公式转化为图。在构造的图中，指定大小的团对应于公式的满足赋值。图中的构造被设计好用来模拟变量和子句的作用。例如：从 3SAT 到 CLIQUEFormula (4 clauses, 4 variables): 4变量 的3子句归约为团由 3 合取范式造对应图的方法设有 k 个子句这里 k=4) (1)

51、 分 k 组画 3k 个顶点，(2) 按子句中变量 标志顶点，(3) 衔接不在同一组中的恣意两顶点(4) 然后把矛盾的边去掉，如上述4步任务可在多项式时间内可完成即 p时间映射归约例如：从 3SAT 到 CLIQUE均True, 是个满足的指派，对应顶点成为团 有 4-clique均True, 是个不满足的指派 非 4-clique当公式为真时，每个3-合取范式中至少一个变量为真，设红箭头所指为真多项式时间可归约性定理7.263SAT 多项式时间可归约到 CLIQUE 。证明：设是 k 个子句的公式，如 = (a1b1 c1) (a2b2 c2) (akbk ck) 归约 f 生成字符串G，k

52、，其中G是如下定义的无向图。G中的结点分成k 组，每组三个结点，称为三元组t1，tk。每个三元组对应于中的一个子句，三个元组中每个结点对应于相应子句的一个文字。G的每个结点用它对应的中的文字做标志。除两种情形以外，G 的边衔接了一切的节点对。同一个三元组内的节点无边相连，相反标志的两个结点无边相连，如x2和 。如今阐明这种构造为何能发扬作用，证明是可满足的当且仅当G有k团。多项式时间可归约性假定有满足赋值。在满足赋值下，每个句子中至少一个文字为真。在 G的每个三元组中，选择在该满足赋值下为真的文字对应的结点。假设在某一子句中不止一个文字为真，恣意选择一个真文字即可。选择出来的结点将恰好构成一个

53、k 团：由于是从 k 个三元组中的每一个中挑选一个结点，所以选择的结点数为k 。每一对选中的结点都有边相连，它们都不适宜前面描画的两种例外情形。它们不能够来自同一三元组，由于从每个三元组中只选一个结点。它们也不能够有相反标志，由于它们关联的文宇在该满足赋值下都为真。所以G 包含k 团。假定 G 有k 团。由于在同一个三元组中的结点都无边相连，所以团中的任何两个结点都不在同一个三元组中。因此 k 个三元组中的每一个都恰好包含团的一个结点。给的 变量赋真值，使得标志团结点的每个文字都为真。这可以办到，由于具有相反标志的两个结点无边相连，所以不能够在两个团中。给变量的这种赋值满足 ，由于每个三元组包

54、含一个团结点，所以每个子句包含一个赋值为TRUE的文字。 可满足。 NP完全性定义 从多项式时间可归约性的定义直接可得。定义7.27假设言语 B 满足下面两个条件，就称为NP完全的：1B 属于 NP，并且2NP 中的每个 A 都多项式时间可归约到 B。定理7.28假设上述的 B 是 NP 完全的，且 BP，那么 P=NP。NP完全性定义知 C 属于 NP，必需证明 NP 中每一个 A 都 多项式时间可归约到 C 。由于 B 是 NP 完全的，所以 NP 中的每个言语都多项式时间可归约到 B，而 B 又多项式时间可归约到 C。 多项式时间归约是可以复合的，即假设 A 多项式时间可归约C ，且 B

55、 多项式时间可归约到 C ，那么 A 多项式时间可归约到C 。因此 NP 中的每个言语都多项式时间可归约到 C 。定理7.29假设上述的 B 是 NP 完全的，且B pC，C 属于 NP，那么 C 是 NP 完全的。库克-列文定理给 NP 中的每一个言语 A 构造一个到 SAT 的多项式时间归约，A 的归约在字符串 w 上产生布尔公式 ，用它模拟 A 的 NP 机器在输入 w上的运转。首先证明 SAT 属于 NP。非确定型多项式时间机器可以猜测给定的公式的一个赋值，当赋值满足时接受。下面，从 NP 中任取一个言语 A，证明 A 多项式可归约到 SAT。设 N 是在时间 nk 内断定A的非确定型

56、图灵机，k 是某个常数。实践假定N 在时间 nk-3在 w 上，N 对应的画面是一张 nk nk 的表格，其中行代表 N 在输入 w 上的一个计算分支的格局。定理7.30SAT 是 NP 完全的。库克-列文定理#q0w1w2wn#nknk起始格局第二个格局第nk个格局窗口库克-列文定理如今描画从 A 到 SAT 的多项式时间归约 f 。在输入w上，该归约产生一个公式。从描画 的变量开场，设 Q 和 是N 的形状集和带字母表，令 C= Q #。对于每个介于1到 nk 之间的 i 和 j 以及 C 中的每个 s，有一个变量 xi, j, s 。假设 xi, j, s 取值 1，那么意味着 cell

57、i, j 包含 s。设计，使得变量的一个满足赋值确实对应 N 在 w 上的一个接受画面。公式是四部分的AND运算： cell start move accept库克-列文定理 start=accept = move 保证，表的每一行都对应于上一行的格局、按照N 的规那么、合法转移得到的格局。它经过每一个23窗口单元都是合法的来保证这一点。如果一个23的窗口不违反由N的转移函数指定的动作，那么称该窗口是合法的。换言之，假设它可以出如今从一个格局正确地转移到另一个格局的过程中，该窗口就称为合法的。库克-列文定理例，设a, b, c是带字母表的成员，q1 和 q2 是 N 的形状 。假设在q1 ，读

58、写头读取 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#baabaabq2bbbcbbaq1baaq2aaq1aab库克-列文定理该机器的不合法窗口：abaaaabq1bq2bq2aq1bq1aa库克-列文定理断言7.31假设表的顶行是起始格局，表中的每一个窗口都是合法的，

59、那么表的每一行都是从上一行合法转移得到的格局。思索表的恣意两个相邻格局，称为上格局和下格局。在上格局中，每一个不与形状符号相邻的而且不含边境符号的单元，都是某个窗口顶行的中间单元且窗口顶行不含形状。因此该符号必定坚持不变，出如今窗口的底行中间，即出如今底行格局的同一位置。窗口顶行的中间单元包含形状符号，这就使相应的三个位置按照转移函数的要求一致更新。因此，假设上格局是合法格局，那么下格局也是，并且下格局是根据 N 的规那么从上格局转移得到。留意，这个证明显然易懂，但它的关键依赖于选择了大小为 23 的窗口。库克-列文定理思索表的恣意两个相邻格局，称为上格局和下格局。断言7.31假设表的顶行是起

60、始格局，表中的每一个窗口都是合法的，那么表的每一行都是从上一行合法转移得到的格局。分析归约的复杂性画面是 nknk 表格，包含 n2k 个单元，每个单元有与它相关联的 l 个变量，l 是 C 中的符号的数目。所以变量总数是O(n2k)。CELL的长度为O(n2k)。 START 的长度为O(nk)。ACCEPT的长度为O(n2k)。 MOVE的长度为O(n2k)。库克-列文定理推论7.323SAT 是 NP 完全的。主要内容7.1 度量复杂性大 O 和小 o 记法、分析算法、模型间的复杂性关系7.2 P类多项式时间、P 中的问题举例7.3 NP类NP中的问题举例、P 与 NP 问题7.4 NP