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

1,引言,Church-Turing论题：能够用总停机的Turing机计算的函数和识别的语言是可计算的（可判定的）；理论可计算计算复杂性理论研究计算模型在各种资源（主要是时间、空间等）限制下的计算能力；实际可计算一个可以计算的问题 需要多少时间和空间？64层次梵塔，1秒钟移动1000片（计算机作），要多少时间？(264-1)/1000=5.846 亿年,2,引言,复杂度和时间：每秒作106的基本运算需要的时间,3,引言,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百年！计算复杂性理论就是要研究计算模型在各种资源限制下的计算能力。将问题划分成Hard and Easy 两大类。,4,引言,co-TM recognizable（补集可识）,TM-recognizable TM decidable,PSPACE,5,主要内容,7.1 度量复杂性大 O 和小 o 记法、分析算法、模型间的复杂性关系7.2 P类多项式时间、P 中的问题举例7.3 NP类NP中的问题举例、P 与 NP 问题7.4 NP完全性多项式时间可归约性、NP 完全性的定义、库克-列文定理7.5 几个NP完全问题顶点覆盖问题、哈密顿路径问题、子集和问题,6,度量复杂性,考察下列例子：语言 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，就接受。考察判定 A 的图灵机 M1 的算法所需的时间。,7,度量复杂性,把算法的运行时间纯粹作为表示输入字符串的长度来计算，而不考虑其它参数。最坏情况分析（worst-case analysis）：考虑在某特定长度的所有输入上的最长运行时间。平均情况分析（average-case analysis）：考虑在某特定长度的所有输入上的运行时间的平均值。,8,度量复杂性,定义7.1,令 M 是一个在所有输入上都停机的确定型图灵机。M 的运行时间或者时间复杂度，是一个函数 f:N N，其中 N 是非负整数集合，f(n)是 M 在所有长度为 n 的输入上运行时所经过的最大步数。若 f(n)是 M 的运行时间，则称 M 在时间 f(n)内运行，M 是时间图灵机。通常使用 n 表示输入的长度。,9,渐进分析,因为算法的精确运行时间通常是一个复杂的表达式，所以一般是估计它的趋势和级别。通过一种称为渐进分析(asymptotic analysis)的方便的估计形式，可以试图了解算法在长输入上的运行时间。只考虑算法运行时间的表达式的最高项，而忽略该项的系数和其它低次项，因为在在长输入上，最高次项的影响相比其它项占据主导地位。例如，函数 f(n)=6n3+2n2+20n+45称 f 渐进地不大于 n3，表达这种关系的渐进记法或大 O 记法是 f(n)=O(n3)。,10,大 O 和小 o记法,定义7.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.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,大 O 和小 o 记法,例7.4 大O记法以一种特别的方式与对数相互影响。通常写对数时必须指明基数(或称为对数的底)，如 x=log2n。这里基数 2 表明该等式等价于等式 2x=n。logbn 的值随着基数 b 的改变而乘以相应的常数倍，因为有恒等式 logbn=log2n/log2b。所以，写 f(n)=O(logn)时不必再指明基数，因为最终要忽略常数因子。,13,大 O 和小 o 记法,令 f2(n)是函数 3nlog2n+5nlog2log2n+2。此时 f2(n)=O(nlogn)，因为 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 2n）2O(1)代表了同样的界，因为表达式 O(1)代表不超过某个固定常数的上界。,14,大O 和小o 记法,我们经常导出 nc 的界，c 是大于 0 的常数。这种界称为多项式界(polynamial bound)。形如 的界，当 是大于 0的实数时，称为指数界(exponential bound)。大 O 记法指一个函数渐近地不大于另一个函数。小 o 记法是渐进的小于另一个函数。大O记法与小o记法的区别类似于和之间的区别。,15,大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)。,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|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,时间复杂性类,语言 A=0k1k|k0，ATIME(n2)，因为 M1 在时间 O(n2)内判定 A，而 TIME(n2)包括所有在时间内可判定的语言。是否存在渐近更快地判定 A 的机器呢？在每次扫描中删除两个 0 和两个 1，如何？,19,分析 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(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)时间内判定的语言都是正则语言。,20,分析M3的时间复杂性,如果图灵机有第二条带，就可以在O(n)时间（也称为线性时间）内判定语言A。下面的两带图灵机TM M3在线性时间内判定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,A 的 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 的运行时间,给出一个单带 TM M1，能够在时间 O(n2)内判定A，以及一个更快的单带 TM M2，能够在时间 O(nlogn)内判定A。两带 TM M3 能在 O(n)时间内判定语言A。因此 A 在单带 TM 上的时间复杂度是 O(nlogn)，在两带TM 上是 O(n)。注意 A 的复杂度与选择的计算模型有关。,23,复杂性理论与可计算性理论的区别,在可计算性理论中，丘奇-图灵论题断言，所有合理的计算模型都是等价的，即它们所判定的语言类都是相同的。在复杂性理论中，模型的选择影响语言的时间复杂度。如在一个模型上线性时间内可判定的语言，在另一个模型上就不一定是线性时间内可判定的。在复杂性理论中，根据计算问题的时间复杂度来对问题分类。,24,模型间的复杂性关系,S 用它的一条带表示 M 的所有k条带的内容。这些带连续存放，M 的读写头的位置都标在恰当的方格上。,25,模型间的复杂性关系,开始时，S 让它的带形成表示 M 的所有带的格式，然后模拟 M 的步骤。为了模拟 M 的一步，S 扫描带上的所有信息，确定在 M 的读写头下的符号。然后 S 再次扫描带，更新带内容和读写头位置。如果 M 的读写头向右移动到带上以前没有读到的位置，那么 S 必须增加分配给这条带的存储空间。为此，它把自己的带的一部分向右移动一格。,26,模型间的复杂性关系,模拟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,模型间的复杂性关系,28,模型间的复杂性关系,设N是一个在时间t(n)内运行的非确定型TM，构造确定型TM D，D通过搜索N 的非确定型计算树来模拟N。在长度为n的输入上，N的非确定型计算树的每一个分支的长度最多是t(n)，树的每一个结点最多有b个子女，其中b是N 的转移函数所决定的合法选择的最大值。因此树叶的总数最多是bt(n)。,输入带,模拟带,地址带,29,模型间的复杂性关系,模拟过程以宽度优先法探查这棵树。换句话说，在访问深度为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)，定理得证。,输入带,模拟带,地址带,30,主要内容,7.1 度量复杂性大 O 和小 o 记法、分析算法、模型间的复杂性关系7.2 P类多项式时间、P 中的问题举例7.3 NP类NP中的问题举例、P 与 NP 问题7.4 NP完全性多项式时间可归约性、NP 完全性的定义、库克-列文定理7.5 几个NP完全问题顶点覆盖问题、哈密顿路径问题、子集和问题,31,多项式时间,定理7.8和定理7.10显示出一个重要的差别。一方面，问题的时间复杂性在确定型单带和多带图灵机上最多是平方或多项式的差异；另一方面，在确定型和非确定型图灵机上，问题的时间复杂性最多是指数差异。典型的指数时间算法来源于通过搜索解空间来求解问题，这称为蛮力搜索（brute-force search）。例如，分解一个数为素数因子的一种方法是搜遍所有可能的因子。搜索空间的规模是指数的，所以这种搜索需要指数时间。有时候，通过更深入地理解问题，可以避免蛮力搜索，从而可能会找到更实用的多项式时间算法。所有合理的确定型计算模型都是多项式等价的（polynomially equivalent），也就是说，它们中任何一个模型都可以模拟另一个，而运行时间只增长多项式倍。当称所有合理的确定型模型都多项式等价时，它足够广泛，能容纳那些和实际计算机运行时间近似的模型。例如，定理7.8表明确定型单带和多带固灵机模型是多项式等价的。,32,多项式时间,在理论中，P类扮演核心的角色，它的重要性在于：1)对于所有与确定型单带图灵机多项式等价的计算模型来说，P是不变的。2)P大致对应于在计算机上实际可解的那一类问题。第1条表明，在数学上，P是一个稳健的类，它不受所采用的具体计算模型的影响。第2条表明，从实用的观点看，P是恰当的。当一个问题在P中的时候，就有办法在时间nk(k是常数)内求解它。至于这么长时间是否实用就依赖于k和实际的应用情况。,33,P中的问题举例,当给出多项式时间算法时，给出的是算法的高层描述，没有提及计算模型的特点，这样做回避了带和读写头运动的繁琐细节。分析一个算法，证明它在多项式时间内运行，需要两步：1)必须为算法在长为 n 的输入上运行时所需要的步骤给出多项式上界（一般用大 O 记法）。2)必须考虑算法描述中的每一步，保证它们都可以由合理的确定型模型在多项式时间内实现。需要注意的问题所用的编码方法。合理的方法就是允许在多项式时间内把对象编码/解码为自然的内部表示或其它合理的编码。图的一种合理编码是它的结点和边的序列。另一种是相邻矩阵，其中若从结点 i 到结点 j 有边，则第(i,j)项为 1，否则为 0。,34,P中的问题举例-PATH,有向图 G 包含结点 s 和 t，如图所示。PATH 问题就是要确定是否存在从 s 到 t 的有向路径。PATH=|G 是具有从 s 到 t 的有向路径的有向图,s,t,35,P中的问题举例-PATH,证明思路：通过给出判定PATH的多项式时间算法来证明该定理。PATH 的蛮力算法通过考察 G 中所有可能路径来确定是否存在从 s 到 t 的有向路径。一条可能路径就是 G 中长度最多为 m 的结点序列，m 是 G 中的节点数。但是这些可能的路径数是 mm，这是 G 中结点数的指数倍。因此该蛮力算法消耗指数时间。为了获得 PATH 的多项式时间算法，必须设法避免蛮力搜索。一种方法是采用图搜索方法，如宽度优先搜索。连续标记 G 中从 s 出发，长度为 1,2,3 直到 m 的有向路径可达的所有节点。用多项式可以容易地来界定该策略的运行时间。,36,PATHP,PATH 的一个多项式时间算法 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,P中的问题举例-RELPRIME,RELPRIME 代表检查两个数是否是互素问题。RELPRIME=|x 与 y 互素,解决该问题的一种算法是搜索这两个数的所有可能的公因子。如果没有发现大于 1 的公因子，就接受。然而，用二进制或其它任何以 k 为基的记法(k2)表示的数字的大小是它表示长度的指数倍。因此该蛮力算法需要搜遍指数多个可能的因子，消耗指数的运行时间。改用一种古老的数值计算过程来求解该问题，称为欧几里德算法(Euclidean algorithm)，来计算最大公因子。两个自然数的最大公因子(greatest common divisor)，即为gcd(x,y)，能同时整除 x 和 y 的最大整数。,38,RELPRIMEP,证明:欧几里德算法 E 如下：E=“对输入，x 和 y 是二进制表示的自然数：1)重复下面的操作，直到 y=0.2)赋值 x x mod y3)交换 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，就接受；否则拒绝。”,39,P中的问题举例-上下文无关语言,证明思路：定理4.8 证明了每一个 CFL 是可判定的，并且为每一个 CFL给出了判定算法。如果那个算法在多项式时间内运行，那么本定理作为推论就必然成立。回忆那个算法，看它运行得是否够快。令 L 是一个由 CFG G 产生的 CFG，G 是乔姆斯基范式。由问题2.26知：因 G 是乔姆斯基范式，任何得到字符串 w 的推导都有 2n-1步，n 是 w 的长度。当给 L 的判定机输入长为 n 的字符串时，它通过试遍所有可能的 2n-1 步推导来判定 L。如果其中有一个得到 w 的推导，该判定机就接受；否则，就拒绝。分析一下该算法可知，它不能在多项式时间内运行。k 步推导的数量可能达到 k 的指数，所以该算法可能需要指数时间。,40,P中的问题举例-上下文无关语言,为了获得多项式时间算法，在此介绍一种强有力的技术，称为动态规划。这种技术通过累积小的子问题的信息来解决大的问题。把子问题的解都记录下来，这样就只需对它求解一次。为此，把所有了问题编成一张表，当碰到它们时，把它们的解系统地填入表格。在本例中，考虑 G 的每一个变元是否产生 w 的每一个子串这样的子问题。算法把子问题的解填入一张 nn表格。对于 ij，表的第(i,j)项包含产生子串 wi wi+1 wj 的所有变元。ij 的表项没有使用。算法为 w 的每一子串填写表项。首先为长为 1 的子串填写表项，然后是长为 2 的子串，依此类推。它利用短子串的表顶内容来辅助确定长子串的表项内容。,41,P中的问题举例-上下文无关语言,例如，假定该算法已经确定了由哪些变元产生所有长度不超过 k 的子串。为了确定变元 A 是否产生某一长为 k+1 的子串，算法把该子串以k种可能方式分裂为非空的两段。对于每一种分裂方式，算法考察每一条规则 A BC，利用以前计算的表项来确定是否 B 产生第一段而且 C 产生第二段。如果 B 和 C 都产生各自的段，那么 A 就产生该子串，并且被加入相关联的表项。算法从长为 1 的串开始，对规则 A b 考察表格。,42,P中的问题举例-上下文无关语言,证明：令G 是产生CFL L的乔姆斯基范式的CFG，假设S是起始变元。D=“对输入w=w1wn:1）若w=且S 是一条规则，则接受。处理w=的情况2）For i=1 to n：考察每一长为1的子串3）对每一个变元 A：4）检查A b是否是一条规则，其中b=wi。5）若是，把A放入table（i，i）。6）For 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）若table（i，k）包含B且table（k+1，j）包含C，则把 A 放入table（i，j）12）若S在table（1，n）中，则接受；否则拒绝。”,43,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,主要内容,7.1 度量复杂性大 O 和小 o 记法、分析算法、模型间的复杂性关系7.2 P类多项式时间、P 中的问题举例7.3 NP类NP中的问题举例、P 与 NP 问题7.4 NP完全性多项式时间可归约性、NP 完全性的定义、库克-列文定理7.5 几个NP完全问题顶点覆盖问题、哈密顿路径问题、子集和问题,45,NP 类,许多问题可以避免使用蛮力搜索而获得多项式时间解法。但是，在某些其它问题中，包括许多有趣而有用的问题，避免蛮力搜索的努力还没有成功，求解它们的多项式时间算法还没有找到。可能这些问题具有未知原理的多项式时间算法，但至今还没有被发现，或者它们中的某些问题就是不能在多项式时间内解决，它们可能是固有地难计算的。一个不寻常的发现是，许多问题的复杂性是联系在一起的。发现其中一个问题的多项式时间算法可以用来解决整个一类问题。,46,多项式可验证性,许多事情,猜出困难，验证易。例如，解方程 x10+2x+7=1035解方程难，验算根x=2容易。HAMPATH=G,s,t|G 是包含从 s 到 t 的哈密顿路径的有向图容易获得指数时间算法，但不知是否能在多项式时间内求解。该问题有一个特点，称为多项式可验证性。虽然还不知道一种快速（即多项式时间）的方法来确定图中是否包含哈密顿路径，但是如果以某种方式（可能是指数时间算法）找到这样的路径，就可以相信它的存在。即：验证哈密顿路径的存在可能比确定它的存在性容易得多。COMPOSITES=x|x=pq，整数 p,q1虽然不知道判断该问题的多项式时间算法，但是容易验证一个数是不是合数-只需要该数的一个因子即可。,47,多项式可验证性,因为只根据 w 的长度来度量验证机的时间，所以多项式时间验证机在 w 的长度的多项式时间内运行。若语言 A 有一个多项式时间验证机，则称它为多项式可验证的。验证机利用额外的信息(在定义7.15中用符号 c 表示)来验证字符串 w 是A 的成员。该信息称为 A 的成员资格证书(certificate)，或证明(proof)。注意，对于多项式验证机，证书具有多项式的长度(w 的长度)，因为这是该验证机在它的时间界限内所能访问的全部信息长度。对于 HAMPATH 问题，字符串 HAMPATH 的证书就只是一条从s 到 t 的哈密顿路径。对于 COMPOSITE 问题，合数 x 的证书只是它的一个因子。,48,NP类,NP 即非确定型多项式时间（nondeterministic polynomial time）。在 NP 中的问题有时被称为 NP 问题。,49,判定 HAMPATH,在非确定型多项式时间内判定 HAMPATH 问题的非确定型图灵机(NTM)：N1=“对输入，这里 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,NP类,一个多项式时间验证机和多项式时间 NTM 相互转换。NTM 通过猜想证书来模拟验证机，验证机通过把接受分支作为证书来模拟 NTM。,51,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 是字符串：1)在输入 w 上模拟 N，把 c 的每一个符号看作是对每一步 所做的非确定性选择的描述。2)若 N 的该计算分支接受，则接受；否则，拒绝。”,52,NP类,53,NP中问题举例CLIQUE,无向图中的团(clique)是一个子图，其中每两个结点都有边相连。k团 就是包含 k 个的结点的团。,4-clique,graph,不是 5-clique,CLIQUE=|G 是包含 k 团的无向图,54,NP中问题举例CLIQUE,证明 下面是 CLIQUE 的验证机 V。V“对输入,c：1)检查 c 是否是 G 中 k 个结点的集合。2)检查 G 是否包含连接 c 中结点的所有边。3)若两项检查都通过，则接受；否则，拒绝。”,团即是证书,另一种证明 通过给出判定 CLIQUE 的图灵机来证明。N“对输入，这里 G 是一个图：1)非确定地选择 G 中 k 个结点的子集 c。2)检查 G 是否包含连接 c 中结点的所有边。3)若是，则接受；否则，拒绝。”,55,NP中问题举例CLIQUE,如果用确定图灵机来解决。Bool DM()G 中有 m 个结点，其中有 k 个结点的子集有mk个，编码排序 1,2,.,mk for(i=1;i mk;i+)/按次序检查子集 c ok=c中两两结点之间的边在 G 中；return ok;说明 确定机用 指数时间，可以解决。但不排除 某个聪明人能找到 确定机 P 时间的方法,56,NP中问题举例SUBSET-SUM,SUBSET-SUM=|s=x1,xk，且存在 y1,yl x1,xk 使得 yi=t x1,xk 和 y1,yl 被看做是多重集，因此允许元素重复。,SUBSET-SUM 不属于 SUBSET-SUM,问题的直观实例(1)不找补 购物(2)装背包，又称背包问题,57,NP中问题举例SUBSET-SUM,证明一 下面是 SUBSET-SUM 的验证机V。V“对输入,c：1)检查 c 是否是加起来等于 t 的数的集合。2)检查 S 是否包含 c 中的所有数。3)若两项检查都通过，则接受；否则，拒绝。”,证明二 通过给出判定SUBSET-SUM的非确定性多项式时间图灵机来证明。N“对输入：1)非确定地选择 S 中的数的子集和 c。2)检查 c 是否是加起来等于 t 的数的集合。3)若检查通过，则接受；否则，拒绝。”,子集即是证书,58,关于 NP 中问题的说明,注意这些集合的补集，和，不是很明显地属于NP。验证某种事物不存在好像要比验证它存在更加困难。我们定义了另外一个复杂性类，称为coNP，它包括 NP 中的语言的补语言。还不知道 coNP 是否与 NP 不同。,59,P 与 NP 问题,P=成员资格可以快速地判定的语言类NP=成员资格可以快速地验证的语言类,NP,P,P=NP,这两个可能中有一个是正确的,求解NP语言的已知的最好方法确定性地使用指数时间。,60,NP完全性,在 P 与 NP 问题上的一个重大进展是在 1970 年代初出斯蒂芬库克（Stephen Cook）和列奥尼德列文（Leonid Levin）完成的。他们发现 NP 中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间算法，那么所有 NP 问题都是多项式时间可解的。这些问题称为 NP完全的（NP-complete）。在理论方面，试图证明 P 不等于 NP 的研究者可以把注意力集中到一个 NP 完全问题上。在实践上，NP 完全性现象可以防止为某一具体问题浪费时间，寻找本不存在的多项式时间算法。,61,NP完全性可满足性问题,布尔变量：取值为 TRUE 和 FALSE，用 1 和 0 表示。布尔运算：AND、OR 和 NOT 分别用、表示。布尔公式：=(x y)(x y)。公式的类型：重言式、矛盾式、可满足式可满足性：对变量的某个 0,1 赋值使得一个公式的值等于1。SAT=|是可满足的布尔公式,该定理把 SAT 问题的复杂性和 NP 中所有问题的复杂性联系起来。,62,多项式时间可归约性,63,多项式时间可归约性,设 M 是判定B 的多项式时间算法，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 在多项式时间内运行是因为两个多项式的合成还是多项式。,64,3SAT,3SAT是可满足性问题的一种特殊情况。文字(literal)：一个布尔变量或布尔变量的非，如 x 或 x。子句(clause)：是由连接起来的若干文字，如(x y z)。合取范式：由连接的若干个子句，亦称为 cnf。,3cnf：所有子句都有三个文字。,3SAT=|是可满足的 3cnf 公式,65,多项式时间可归约性,证明思路：给出从 3SAT 到 CLIQUE 的多项式时间归约 f，它把公式转化为图。在构造的图中，指定大小的团对应于公式的满足赋值。图中的结构被设计好用来模拟变量和子句的作用。,66,示例：从 3SAT 到 CLIQUE,Formula(4 clauses,4 variables):4变量 的3子句归约为团,由 3 合取范式造对应图的方法设有 k 个子句（这里 k=4)(1)分 k 组画 3k 个顶点，(2)按子句中变量 标记顶点，(3)连接不在同一组中的任意两顶点,(4)然后把矛盾的边去掉，如上述4步工作可在多项式时间内可完成即 p时间映射归约,67,示例：从 3SAT 到 CLIQUE,均True,是个满足的指派，对应顶点成为团,均True,是个不满足的指派,当公式为真时，每个3-合取范式中至少一个变量为真，设红箭头所指为真,68,多项式时间可归约性,证明：设是 k 个子句的公式，如=(a1b1 c1)(a2b2 c2)(akbk ck)归约 f 生成字符串G，k，其中G是如下定义的无向图。G中的结点分成k 组，每组三个结点，称为三元组t1，tk。每个三元组对应于中的一个子句，三个元组中每个结点对应于相应子句的一个文字。G的每个结点用它对应的中的文字做标记。除两种情形以外，G 的边连接了所有的节点对。同一个三元组内的节点无边相连，相反标记的两个结点无边相连，如x2和。现在说明这种构造为何能发挥作用，证明是可满足的当且仅当G有k团。,69,多项式时间可归约性,假定有满足赋值。在满足赋值下，每个句子中至少一个文字为真。在 G的每个三元组中，选择在该满足赋值下为真的文字对应的结点。如果在某一子句中不止一个文字为真，任意选择一个真文字即可。选择出来的结点将恰好形成一个k 团：因为是从 k 个三元组中的每一个中挑选一个结点，所以选择的结点数为k。每一对选中的结点都有边相连，它们都不适合前面描述的两种例外情形。它们不可能来自同一三元组，因为从每个三元组中只选一个结点。它们也不可能有相反标记，因为它们关联的文宇在该满足赋值下都为真。所以G 包含k 团。假定 G 有k 团。因为在同一个三元组中的结点都无边相连，所以团中的任何两个结点都不在同一个三元组中。因此 k 个三元组中的每一个都恰好包含团的一个结点。给的 变量赋真值，使得标记团结点的每个文字都为真。这可以办到，因为具有相反标记的两个结点无边相连，所以不可能在两个团中。给变量的这种赋值满足，因为每个三元组包含一个团结点，所以每个子句包含一个赋值为TRUE的文字。可满足。,70,NP完全性定义,从多项式时间可归约性的定义直接可得。,如果语言 B 满足下面两个条件，就称为NP完全的：1）B 属于 NP，并且2）NP 中的每个 A 都多项式时间可归约到 B。,71,NP完全性定义,已知 C 属于 NP，必须证明 NP 中每一个 A 都 多项式时间可归约到 C。因为 B 是 NP 完全的，所以 NP 中的每个语言都多项式时间可归约到 B，而 B 又多项式时间可归约到 C。多项式时间归约是可以复合的，即若 A 多项式时间可归约C，且 B 多项式时间可归约到 C，则 A 多项式时间可归约到C。因此 NP 中的每个语言都多项式时间可归约到 C。,72,库克-列文定理,给 NP 中的每一个语言 A 构造一个到 SAT 的多项式时间归约，A 的归约在字符串 w 上产生布尔公式，用它模拟 A 的 NP 机器在输入 w上的运行。首先证明 SAT 属于 NP。非确定型多项式时间机器可以猜测给定的公式的一个赋值，当赋值满足时接受。下面，从 NP 中任取一个语言 A，证明 A 多项式可归约到 SAT。设 N 是在时间 nk 内判定A