计算理论导引__时间复杂性

1、朴秀峰朴秀峰计算理论1引言q Church-Turing论题论题：能够用总停机的：能够用总停机的Turing机计算的函数机计算的函数和识别的语言是可计算的（可判定的）；和识别的语言是可计算的（可判定的）；理论可计算理论可计算q 计算复杂性理论计算复杂性理论研究计算模型在各种资源（主要是研究计算模型在各种资源（主要是时间时间、空间空间等）限制下的计算能力；等）限制下的计算能力； 实际可计算实际可计算q 一个可以计算的问题一个可以计算的问题 需要多少时间和空间？需要多少时间和空间？q 64层次梵塔，层次梵塔，1秒钟移动秒钟移动1000片（计算机作），要多少时间？片（计算机作），要多少时间？q (

2、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世纪世纪3N

3、0.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*

4、1023.假设用一台超假设用一台超级计算机计算，每秒可以检查级计算机计算，每秒可以检查1亿个排列。每年有亿个排列。每年有3.15*107秒，不停地工作，秒，不停地工作，每年可以检查每年可以检查3.15*1015个排列。检查完所有的排列需要个排列。检查完所有的排列需要1.97*108年，即年，即1亿亿9千千7百年！百年！q 计算复杂性理论就是要研究计算模型在各种资源限制下的计算能力。将问题划计算复杂性理论就是要研究计算模型在各种资源限制下的计算能力。将问题划分成分成Hard and Easy 两大类。两大类。4引言co-TM recognizable（补集可识）TM-recognizable T

5、M decidable PSPACE co-NPNP P5主要内容主要内容7.1 度量复杂性度量复杂性大大 O 和小和小 o 记法、分析算法、模型间的复杂性关系记法、分析算法、模型间的复杂性关系7.2 P类类多项式时间、多项式时间、P 中的问题举例中的问题举例7.3 NP类类NP中的问题举例、中的问题举例、P 与与 NP 问题问题7.4 NP完全性完全性多项式时间可归约性、多项式时间可归约性、NP 完全性的定义、库克完全性的定义、库克-列文定理列文定理7.5 几个几个NP完全问题完全问题顶点覆盖问题、哈密顿路径问题、子集和问题顶点覆盖问题、哈密顿路径问题、子集和问题6度量复杂性q 考察下列例子

6、：考察下列例子：语言语言 A = 0k1k | k 0 ，显然，显然 A 是一个可判定的语言。是一个可判定的语言。考察下面判定考察下面判定A的单带的单带 TM M1M1=“对于输入串对于输入串 w：1) 扫描带子，如果在扫描带子，如果在 1 的右边发现的右边发现 0，就，就拒绝拒绝。2) 如果带上既有如果带上既有 0 也有也有 1，就重复下一步。，就重复下一步。3) 扫描带子，删除一个扫描带子，删除一个 0 和一个和一个 1。4) 如果所有如果所有 1 都被删除以后还有都被删除以后还有 0，或者所有，或者所有 0 都被删除以后还有都被删除以后还有 1，就，就拒绝拒绝。否则，如果在带上既没有剩下

7、。否则，如果在带上既没有剩下0也没有剩下也没有剩下 1，就，就接受接受。q 考察判定考察判定 A 的图灵机的图灵机 M1 的算法所需的时间。的算法所需的时间。7度量复杂性q 把把算法的运行时间算法的运行时间纯粹作为表示纯粹作为表示输入字符串的长度输入字符串的长度来计算，来计算，而不考虑其它参数。而不考虑其它参数。q 最坏情况分析（最坏情况分析（worst-case analysis）：考虑在某特定长度：考虑在某特定长度的所有输入上的最长运行时间。的所有输入上的最长运行时间。q 平均情况分析（平均情况分析（average-case analysis）：考虑在某特定长：考虑在某特定长度的所有输入上

8、的运行时间的平均值。度的所有输入上的运行时间的平均值。8度量复杂性令令 M 是一个在所有输入上都停机的确定型图灵机。是一个在所有输入上都停机的确定型图灵机。M 的的运行时间运行时间或者或者时间复杂度时间复杂度，是一个函数，是一个函数 f : N N，其中，其中 N 是非负整数集合，是非负整数集合， f(n) 是是 M 在在所有长度为所有长度为 n 的输入上运行时所经过的最大步数的输入上运行时所经过的最大步数。若若 f(n) 是是 M 的运行时间，则称的运行时间，则称 M 在时间在时间 f(n) 内运内运行，行，M 是时间图灵机。是时间图灵机。通常使用通常使用 n 表示输入的长度。表示输入的长度

9、。9渐进分析q 因为算法的精确运行时间通常是一个复杂的表达式，所以因为算法的精确运行时间通常是一个复杂的表达式，所以一般是估计它的趋势和级别。一般是估计它的趋势和级别。q 通过一种称为通过一种称为渐进分析渐进分析 (asymptotic analysis) 的方便的估计的方便的估计形式，可以试图了解算法在长输入上的运行时间。形式，可以试图了解算法在长输入上的运行时间。q 只考虑算法运行时间的表达式的最高项，而忽略该项的系只考虑算法运行时间的表达式的最高项，而忽略该项的系数和其它低次项，因为在在长输入上，数和其它低次项，因为在在长输入上，最高次项最高次项的影响相的影响相比其它项比其它项占据主导地

10、位占据主导地位。q 例如，函数例如，函数 f (n) = 6n3+2n2+20n+45称称 f 渐进地不大于渐进地不大于 n3，表达这种关系的，表达这种关系的渐进记法渐进记法或大或大 O 记记法法是是 f (n) = O(n3)。 10大 O 和小 o记法设设 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、的渐近上界，以强调没有考虑以强调没有考虑常数因子。常数因子。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)，不论给，

12、不论给 c 和和 n0 赋什么值，始终不满足赋什么值，始终不满足定义的要求。定义的要求。12大 O 和小 o 记法例例7.4 大大O记法以一种特别的方式与对数相互记法以一种特别的方式与对数相互影响。影响。通常通常写对数时必须写对数时必须指明基数指明基数(或称为对数的底或称为对数的底)，如，如 x=log2n 。这里基数这里基数 2 表明表明该等式等价该等式等价于等式于等式 2x=n。logbn 的的值值随着基数随着基数 b 的的改变而乘以相应的常数倍，因为改变而乘以相应的常数倍，因为有恒等式有恒等式 logbn = log2n / log2b。所以，写。所以，写 f(n) = O(logn)

13、时时不必再指明基数，因为不必再指明基数，因为最终最终要忽略常数因子。要忽略常数因子。13大 O 和小 o 记法q 令令 f2(n) 是函数是函数 3nlog2n+5nlog2log2n+2。 此时此时 f2(n) =O(nlogn)，因为，因为 logn 比比 log logn更占支配位置。更占支配位置。q f(n) =O(n2)+ O(n) 等价于等价于 f(n) =O(n2)q 当当 O 出现在指数位置，如出现在指数位置，如 f(n) =2O(n)，代表着，代表着 2cn 的一个上的一个上界。界。q f(n) =2O(logn)，代表，代表 nc。（由。（由 n = 2log n 得得 n

14、c = 2c log 2n）q 2O(1) 代表了同样的界，因为表达式代表了同样的界，因为表达式 O(1) 代表不超过某个固代表不超过某个固定常数的上界。定常数的上界。14大O 和小o 记法q 我们经常导出我们经常导出 nc 的界，的界，c 是大于是大于 0 的常数。这种界称为的常数。这种界称为多多项式界项式界 (polynamial bound)。形如。形如 的界，当的界，当 是大于是大于 0的实数时，称为的实数时，称为指数界指数界(exponential bound)。q 大大 O 记法记法指一个函数渐近地指一个函数渐近地不大于不大于另一个函数。另一个函数。q 小小 o 记法记法是渐进的是

15、渐进的小于小于另一个函数。另一个函数。q 大大O记法与小记法与小o记法的区别类似于记法的区别类似于和之间的区别。和之间的区别。2n15大O 和小o 记法设设 f 和和 g 是两个函数是两个函数 f , g : N R+，如果，如果则称则称 f (n) = o(g(n)。换言之，。换言之，f (n) = o(g(n) 意味着意味着对于任何实数对于任何实数 c0，存在一个数，存在一个数 n0，使得对所有，使得对所有 nn0，f (n)cg(n)。( )lim0( )nf ng n16大O 和小o 记法例例7.6 容易验证下面的等式。容易验证下面的等式。 1) 2) n = o(nlog(logn)

16、 3) nlog(logn) = o(nlogn) 4) nlogn = o(n2) 5) n2 = o(n3) 但是，但是，f(n) 不会等于不会等于o(f(n) 。( )no n17分析算法分析语言分析语言 A = 0k1k | k 0 对应的图灵机算法。对应的图灵机算法。M1 = “对于输入串对于输入串 w：1) 扫描带子，如果在扫描带子，如果在 1 的右边发现的右边发现 0，就，就拒绝拒绝。2) 如果带上既有如果带上既有 0 也有也有 1，就重复下一步。，就重复下一步。3) 扫描带子，删除一个扫描带子，删除一个 0 和一个和一个 1。4) 如果所有如果所有 1 都被删除以后还有都被删除

17、以后还有 0，或者所有，或者所有 0 都被删除以后还有都被删除以后还有 1，就就拒绝拒绝。否则，如果在带上既没有剩下。否则，如果在带上既没有剩下 0 也没有剩下也没有剩下 1，就，就接受接受。 q 步骤步骤1中，机器扫描带以验证输入的形式是中，机器扫描带以验证输入的形式是0*1*。执行这次扫描需要。执行这次扫描需要n步步。读写头重新放置在带的左端另外需要读写头重新放置在带的左端另外需要n步步。共需要。共需要2n步步。即。即O(n)步。步。q 在步骤在步骤2和和3中，机器反复扫描带，在每一次扫描中删除一个中，机器反复扫描带，在每一次扫描中删除一个0和一个和一个1。每一次扫描需要每一次扫描需要O(

18、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时间复杂性类令令 t : N R+ 是一个函数。定义是一个函数。定义时间复杂性类时间复杂

19、性类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

20、(nlogn)。M2=“对输入串对输入串 w：1) 扫描带，如果扫描带，如果 1 的右边发现的右边发现 0，就，就拒绝拒绝。2) 只要在带上还有只要在带上还有 0 和和 1，就重复下面的步骤。，就重复下面的步骤。3) 扫描带，检查剩余的扫描带，检查剩余的 0 和和 1 的总数是偶数还是奇数。的总数是偶数还是奇数。 若是奇数，就若是奇数，就拒绝拒绝。4) 再次扫描带，从第一个再次扫描带，从第一个 0 开始，开始，隔一个删除一个隔一个删除一个 0； 然后从第一个然后从第一个 1 开始，开始，隔一个删除一个隔一个删除一个 1.5) 如果带上不再有如果带上不再有 0 和和 1，就，就接受接受。否则。否

21、则拒绝拒绝。”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)。 q ATIME(nlogn)。这个结果在单带图灵机上不可能进一步改进。这个结果在

22、单带图灵机上不可能进一步改进。q 单带图灵机在单带图灵机在o(nlogn)时间内判定的语言都是正则语言时间内判定的语言都是正则语言。20分析M3的时间复杂性q 如果图灵机有第二条带，就可以在如果图灵机有第二条带，就可以在O(n)时间（也称为线性时间）内判定时间（也称为线性时间）内判定语言语言A。下面的两带图灵机。下面的两带图灵机TM M3在线性时间内判定在线性时间内判定A。M3 = “ 对于输入串对于输入串 w：1) 扫描带，如果扫描带，如果 1 的右边发现的右边发现 0，就，就拒绝拒绝。2) 扫描带扫描带 1 上的上的 0，直到第一个，直到第一个 1 时停止，同时把时停止，同时把 0 复制到

23、带复制到带 2 上。上。3) 扫描带扫描带 1 上的上的 1 直到输入的末尾。每次从带直到输入的末尾。每次从带 1 上读到一个上读到一个 1，就在带，就在带 2 上删除一个上删除一个 0，如果在读完，如果在读完 1 之前所有的之前所有的 0 都被删除，就都被删除，就拒绝拒绝。4) 如果所有如果所有 0 都被删除，就都被删除，就接受接受。如果还有。如果还有 0 剩下，就剩下，就拒绝拒绝。”q 四个步骤中每一步需要四个步骤中每一步需要O(n)步，所以全部的运行时间是步，所以全部的运行时间是O(n)，因而是，因而是线性的。线性的。q 注意，这可能是最好的运行时间，因为光是读输入就需要注意，这可能是最

24、好的运行时间，因为光是读输入就需要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)时间. 使用的资源:随机存取,数组

25、，两带图灵机，22总结 A 的运行时间q 给出一个单带给出一个单带 TM M1，能够在时间，能够在时间 O(n2)内判定内判定A，以及一，以及一个更快的单带个更快的单带 TM M2，能够在时间，能够在时间 O(nlogn)内判定内判定A。两。两带带 TM M3 能在能在 O(n) 时间内判定语言时间内判定语言A。q 因此因此 A 在单带在单带 TM 上的时间复杂度是上的时间复杂度是 O(nlogn)，在两带，在两带TM 上是上是 O(n)。q 注意注意 A 的复杂度与选择的计算模型有关。的复杂度与选择的计算模型有关。23复杂性理论与可计算性理论的区别q 在在可计算性理论可计算性理论中，丘奇中，

26、丘奇-图灵论题断言，图灵论题断言，所有合理的计算所有合理的计算模型都是等价的模型都是等价的，即它们所判定的语言类都是相同的。，即它们所判定的语言类都是相同的。q 在在复杂性理论复杂性理论中，中，模型的选择影响语言的时间复杂度模型的选择影响语言的时间复杂度。如。如在一个模型上线性时间内可判定的语言，在另一个模型上在一个模型上线性时间内可判定的语言，在另一个模型上就不一定是线性时间内可判定的。就不一定是线性时间内可判定的。q 在复杂性理论中，在复杂性理论中，根据计算问题的时间复杂度来对问题分根据计算问题的时间复杂度来对问题分类类。24模型间的复杂性关系设设 t(n) 是一个函数，是一个函数， t(

27、n)n。则每一个时间。则每一个时间 t(n)的的多带多带图灵机都和某一个图灵机都和某一个 O(t2(n) 时间的时间的单带单带图灵机图灵机等价。等价。S 用它的一条带表示用它的一条带表示 M 的所有的所有k条带条带的内容。这些带连续存放，的内容。这些带连续存放， M 的读的读写头的位置都标在恰当的方格上。写头的位置都标在恰当的方格上。01010Maaa ba #01010#aaa#ba# S25模型间的复杂性关系01010Maaa ba #01010#aaa#ba# S开始时，开始时， S 让它的带形成表示让它的带形成表示 M 的所有带的格式，然后模拟的所有带的格式，然后模拟 M 的步骤。的步

28、骤。为了模拟为了模拟 M 的一步，的一步， S 扫描带上的所有信息，扫描带上的所有信息，确定在确定在 M 的读写头下的符的读写头下的符号号。然后。然后 S 再次扫描带，再次扫描带，更新带内容和读写头位置更新带内容和读写头位置。如果。如果 M 的读写头向右的读写头向右移动到带上以前没有读到的位置，那么移动到带上以前没有读到的位置，那么 S 必须增加分配给这条带的存储空必须增加分配给这条带的存储空间。为此，它把自己的带的一部分向右移动一格。间。为此，它把自己的带的一部分向右移动一格。26模型间的复杂性关系01010Maaa ba #01010#aaa#ba# S模拟模拟M 的每一步，的每一步，S执

29、行两次扫描，执行两次扫描，还可能最多向右移动还可能最多向右移动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)步。因此，整个的模步。因此，整个的模拟过程需要拟

30、过程需要O(n)+ O(t2(n)步。步。假定假定t(n) n（这是合理的假定，因为如果时间更少，（这是合理的假定，因为如果时间更少， M连输入都读不完）连输入都读不完），则，则S的运行时间是的运行时间是O(t2(n)，证毕。，证毕。27模型间的复杂性关系设设 N 是一个非确定型图灵机，并且是一个判定机。是一个非确定型图灵机，并且是一个判定机。N 的运行时间是函数的运行时间是函数 f : NN ，其中其中 f(n) 是在任何是在任何长度为长度为 n 的输入上所有的计算分支中最大步数的输入上所有的计算分支中最大步数。28模型间的复杂性关系设设 t(n) 是一个函数，是一个函数， t(n)n 。则

31、每一个。则每一个 t(n) 时间时间的的非确定型单带图灵机非确定型单带图灵机都与某一都与某一 2O(t(n) 时间时间的确定的确定型图灵机型图灵机等价。等价。设设N是一个在时间是一个在时间t(n)内运行的非确定型内运行的非确定型TM ，构造确定型，构造确定型TM D，D通过搜索通过搜索N 的非确定型计算树来模拟的非确定型计算树来模拟N。 在长度为在长度为n的输入上，的输入上，N的非确定型计算树的非确定型计算树的的每一个分支的长度最多是每一个分支的长度最多是t(n) ，树的，树的每一个结点最多有每一个结点最多有b个子女个子女，其中，其中b是是N 的转移函数所决定的合法选择的最大值。因此的转移函数

32、所决定的合法选择的最大值。因此树叶的总数最多是树叶的总数最多是bt(n) 。0010Dxx#01x 12332312113 输入带模拟带地址带29模型间的复杂性关系模拟过程以宽度优先法探查这棵树。换句话说，在访问深度为模拟过程以宽度优先法探查这棵树。换句话说，在访问深度为d+1的结点之的结点之前，先访问所有深度为前，先访问所有深度为d 的结点。的结点。树中结点的总数小于最大叶数的两倍，因此用树中结点的总数小于最大叶数的两倍，因此用O(bt(n)作它的上界。作它的上界。从根出发下行到一个结点的时间是从根出发下行到一个结点的时间是O(t(n) 。因此，因此，D的运行时间是的运行时间是O(t(n)

33、bt(n) = 2O(t(n) 。TM D有三条带。把它转变为单带有三条带。把它转变为单带TM，最多使运行时间乘方。这样，单带模，最多使运行时间乘方。这样，单带模拟机的运行时间是拟机的运行时间是(2O(t(n)2 = 2O(2t(n) = 2O(t(n) ，定理得证。，定理得证。 0010Dxx#01x 12332312113 输入带模拟带地址带30主要内容主要内容7.1 度量复杂性度量复杂性大大 O 和小和小 o 记法、分析算法、模型间的复杂性关系记法、分析算法、模型间的复杂性关系7.2 P类类多项式时间、多项式时间、P 中的问题举例中的问题举例7.3 NP类类NP中的问题举例、中的问题举例

34、、P 与与 NP 问题问题7.4 NP完全性完全性多项式时间可归约性、多项式时间可归约性、NP 完全性的定义、库克完全性的定义、库克-列文定理列文定理7.5 几个几个NP完全问题完全问题顶点覆盖问题、哈密顿路径问题、子集和问题顶点覆盖问题、哈密顿路径问题、子集和问题31多项式时间q 定理定理7.8和定理和定理7.10显示出一个重要的差别。一方面，问题的时间复杂性显示出一个重要的差别。一方面，问题的时间复杂性在在确定型单带和多带图灵机确定型单带和多带图灵机上最多是平方或上最多是平方或多项式多项式的差异；另一方面，的差异；另一方面，在在确定型和非确定型图灵机确定型和非确定型图灵机上，问题的时间复杂

35、性最多是上，问题的时间复杂性最多是指数指数差异。差异。q 典型的指数时间算法来源于通过搜索解空间来求解问题，这称为典型的指数时间算法来源于通过搜索解空间来求解问题，这称为蛮力搜蛮力搜索（索（brute-force search）。例如，分解一个数为素数因子的一种方法是。例如，分解一个数为素数因子的一种方法是搜遍所有可能的因子。搜索空间的规模是指数的，所以这种搜索需要指搜遍所有可能的因子。搜索空间的规模是指数的，所以这种搜索需要指数时间。有时候，通过更深入地理解问题，可以避免蛮力搜索，从而可数时间。有时候，通过更深入地理解问题，可以避免蛮力搜索，从而可能会找到更实用的多项式时间算法。能会找到更实

36、用的多项式时间算法。q 所有合理的确定型计算模型都是所有合理的确定型计算模型都是多项式等价的（多项式等价的（polynomially equivalent），也就是说，它们中任何一个模型都可以模拟另一个，而运，也就是说，它们中任何一个模型都可以模拟另一个，而运行时间只增长多项式倍。行时间只增长多项式倍。当称所有合理的确定型模型都多项式等价时当称所有合理的确定型模型都多项式等价时，它足够广泛，它足够广泛，能容纳那些和实际计算机运行时间近似的模型能容纳那些和实际计算机运行时间近似的模型。例如，定。例如，定理理7.8表明确定型单带和多带固灵机模型是多项式等价的。表明确定型单带和多带固灵机模型是多项式

37、等价的。32多项式时间在理论中，在理论中，P类扮演核心的角色，它的重要性在于：类扮演核心的角色，它的重要性在于：1)对于所有与确定型单带图灵机多项式等价的计算模型来说，对于所有与确定型单带图灵机多项式等价的计算模型来说，P是不变的。是不变的。2)P大致对应于在计算机上实际可解的那一类问题。大致对应于在计算机上实际可解的那一类问题。第第1条表明，在数学上，条表明，在数学上，P是一个稳健的类，它不受所采用的具体计算模型是一个稳健的类，它不受所采用的具体计算模型的影响。的影响。第第2条表明，从实用的观点看，条表明，从实用的观点看，P是恰当的。当一个问题在是恰当的。当一个问题在P中的时候，就中的时候，

38、就有办法在时间有办法在时间nk(k是常数是常数)内求解它。至于这么长时间是否实用就依赖于内求解它。至于这么长时间是否实用就依赖于k和和实际的应用情况。实际的应用情况。P 是是确定型单带图灵机确定型单带图灵机在在多项式时间内可判定多项式时间内可判定的语的语言类。换言之，言类。换言之， P TIME(nk)k33P中的问题举例q 当给出多项式时间算法时，给出的是算法的高层描述，没有当给出多项式时间算法时，给出的是算法的高层描述，没有提及计算模型的特点，这样做回避了带和读写头运动的繁琐提及计算模型的特点，这样做回避了带和读写头运动的繁琐细节。细节。q 分析一个算法，证明它在多项式时间内运行，需要两步

39、：分析一个算法，证明它在多项式时间内运行，需要两步：1) 必须为算法在长为必须为算法在长为 n 的输入上运行时所需要的步骤给出多的输入上运行时所需要的步骤给出多项式上界（一般用大项式上界（一般用大 O 记法）。记法）。2) 必须考虑算法描述中的每一步，保证它们都可以由合理的必须考虑算法描述中的每一步，保证它们都可以由合理的确定型模型在多项式时间内实现。确定型模型在多项式时间内实现。q 需要注意的问题所用的编码方法。合理的方法就是允许在多需要注意的问题所用的编码方法。合理的方法就是允许在多项式时间内把对象编码项式时间内把对象编码/解码为自然的内部表示或其它合理的解码为自然的内部表示或其它合理的编

40、码。编码。q 图的一种合理编码是它的结点和边的序列。另一种是相邻矩图的一种合理编码是它的结点和边的序列。另一种是相邻矩阵，其中若从结点阵，其中若从结点 i 到结点到结点 j 有边，则第有边，则第 ( i , j ) 项为项为 1，否则，否则为为 0。34P中的问题举例-PATH有向图有向图 G 包含结点包含结点 s 和和 t ，如图所示。，如图所示。PATH 问题问题就是要就是要确定是否存在从确定是否存在从 s 到到 t 的有向路径的有向路径。PATH = | G 是具有从是具有从 s 到到 t 的有向路径的有向图的有向路径的有向图st35P中的问题举例-PATHPATHP 证明思路：证明思路

41、： 通过给出判定通过给出判定PATH的多项式时间算法来证明该定理。的多项式时间算法来证明该定理。PATH 的蛮力算法的蛮力算法通过通过考察考察 G 中所有可能路径来确定是否存在从中所有可能路径来确定是否存在从 s 到到 t 的的有向路径有向路径。一条可能路径就是一条可能路径就是 G 中长度最多为中长度最多为 m 的结点序列，的结点序列， m 是是 G 中的节点数。中的节点数。但是这些可能的路径数是但是这些可能的路径数是 mm，这是，这是 G 中结点数的指数倍。因此该蛮力算中结点数的指数倍。因此该蛮力算法消耗指数时间。法消耗指数时间。为了获得为了获得 PATH 的多项式时间算法，必须设法避免蛮力

42、搜索。一种方法是的多项式时间算法，必须设法避免蛮力搜索。一种方法是采用图搜索方法，如宽度优先搜索。连续标记采用图搜索方法，如宽度优先搜索。连续标记 G 中从中从 s 出发，长度为出发，长度为 1, 2, 3 直到直到 m 的有向路径可达的所有节点。的有向路径可达的所有节点。用多项式可以容易地来界定该策略的运行时间。用多项式可以容易地来界定该策略的运行时间。36PATHPPATH 的一个多项式时间算法的一个多项式时间算法 M 运行如下：运行如下：M“对输入对输入 G, s, t，G 是包含结点是包含结点 s 和和 t 的有向图：的有向图： 1) 在结点在结点 s 上做标记。上做标记。 2) 复重

43、下面步骤复重下面步骤 3，直到不再有结点被标记。，直到不再有结点被标记。 3) 扫描扫描 G 的所有边。如果找到一条边的所有边。如果找到一条边 (a, b)， a 被标记，被标记， 而而 b 没有被标记，那么标记没有被标记，那么标记 b。 4) 若若 t 被标记，则被标记，则接受接受；否则，；否则，拒绝拒绝。”步骤步骤 1 和和 4 只执行一次只执行一次。步骤步骤 3 最多执行最多执行 m 次次，因为除最后一次外，每一，因为除最后一次外，每一次执行都要标记次执行都要标记 G 中的一个未标记的结点。所以用到的总步数最多是中的一个未标记的结点。所以用到的总步数最多是1+1+m，是，是 G 的规模的

44、多项式。的规模的多项式。 M 的步骤的步骤 1 和和 4 很容易用任问合理的确定型模型在多项式时间内实现。很容易用任问合理的确定型模型在多项式时间内实现。步骤步骤 3 需要扫描输入，检查某些结点是否被标记，这也容易在多项式时间需要扫描输入，检查某些结点是否被标记，这也容易在多项式时间内实现。所以内实现。所以 M 是是 PATH 的多项式时间算法。的多项式时间算法。 37P中的问题举例- RELPRIMERELPRIME 代表检查两个数是否是互素问题。代表检查两个数是否是互素问题。RELPRIME = | x 与与 y 互素互素RELPRIMEP 解决该问题的一种算法是搜索这两个数的所有可能的公

45、因子。如果没有发解决该问题的一种算法是搜索这两个数的所有可能的公因子。如果没有发现大于现大于 1 的公因子，就接受。然而，用二进制或其它任何以的公因子，就接受。然而，用二进制或其它任何以 k 为基的记法为基的记法(k2) 表示的数字的大小是它表示长度的指数倍。因此该蛮力算法需要搜遍表示的数字的大小是它表示长度的指数倍。因此该蛮力算法需要搜遍指数多个可能的因子，消耗指数的运行时间。指数多个可能的因子，消耗指数的运行时间。改用一种古老的数值计算过程来求解该问题，称为改用一种古老的数值计算过程来求解该问题，称为欧几里德算法欧几里德算法(Euclidean algorithm)，来计算最大公因子。两个

46、自然数的，来计算最大公因子。两个自然数的最大公因子最大公因子(greatest common divisor)，即为，即为gcd(x, y)，能同时整除，能同时整除 x 和和 y 的最大整数。的最大整数。38RELPRIMEP 证明证明: 欧几里德算法欧几里德算法 E 如下：如下：E=“对输入对输入，x 和和 y 是二进制表示的自然数：是二进制表示的自然数：1) 重复下面的操作，直到重复下面的操作，直到 y=0.2) 赋值赋值 x x mod y3) 交换交换 x 和和 y4) 输出输出 x。”显然，若显然，若 E 在多项式时间内运行且正确，则在多项式时间内运行且正确，则 R 也在多项式时间内

47、运行且正也在多项式时间内运行且正确。所以只需分析确。所以只需分析 E 的时间和正确性。的时间和正确性。步骤步骤2的每一次执行的每一次执行(除了第一次有可能例外除了第一次有可能例外)，都把，都把 x 的值至少减少一半。的值至少减少一半。 每一次执行步骤每一次执行步骤 3都使都使 x 和和 y 的值相互交换，所以每两次循环就使得的值相互交换，所以每两次循环就使得 x 和和 y原先的值至少减少一半。于是步骤原先的值至少减少一半。于是步骤 2 和和 3 执行的最大次数是执行的最大次数是 2log2x 和和 2log2y 中较小的那一个。这两个对数与表示的长度成正比，步骤的执行次数中较小的那一个。这两个

48、对数与表示的长度成正比，步骤的执行次数是是 O(n)。 E 的每一步仅消耗多项式时间，所以整个运行时间是多项式的。的每一步仅消耗多项式时间，所以整个运行时间是多项式的。算法算法 R 以以 E 为子程序求解为子程序求解 RELPRIMER=“对输入对输入 ，x 和和 y 是二进制表示的自然数：是二进制表示的自然数： 1) 在在 上运行上运行E。 2) 若结果为若结果为 1，就，就接受接受；否则；否则拒绝拒绝。”39P中的问题举例-上下文无关语言每一个上下文无关语言都是每一个上下文无关语言都是 P 的成员。的成员。证明思路：证明思路： 定理定理4.8 证明了每一个证明了每一个 CFL 是可判定的，

49、并且为每一个是可判定的，并且为每一个 CFL给出了判定算法。如果那个算法在多项式时间内运行，那么本定理作为推给出了判定算法。如果那个算法在多项式时间内运行，那么本定理作为推论就必然成立。回忆那个算法，看它运行得是否够快。论就必然成立。回忆那个算法，看它运行得是否够快。 令令 L 是一个由是一个由 CFG G 产生的产生的 CFG，G 是乔姆斯基范式。由问题是乔姆斯基范式。由问题2.26知：因知：因 G 是乔姆斯基范式，是乔姆斯基范式，任何得到字符串任何得到字符串 w 的推导都有的推导都有 2n-1步步，n 是是 w 的长度。当给的长度。当给 L 的判定机输入长为的判定机输入长为 n 的字符串时

50、，它的字符串时，它通过试遍所有可能的通过试遍所有可能的 2n-1 步推导来判定步推导来判定 L。如果其中有一个得到。如果其中有一个得到 w 的推导，该判定机就接受；的推导，该判定机就接受；否则，就拒绝。否则，就拒绝。 分析一下该算法可知，它不能在多项式时间内运行。分析一下该算法可知，它不能在多项式时间内运行。 k 步推导的数量步推导的数量可能达到可能达到 k 的指数，所以该算法可能需要指数时间。的指数，所以该算法可能需要指数时间。40P中的问题举例-上下文无关语言为了获得多项式时间算法，在此介绍一种强有力的技术，称为为了获得多项式时间算法，在此介绍一种强有力的技术，称为动态规划动态规划。这种技

51、术通过累积小的子问题的信息来解决大的问题。把子问题的解都记这种技术通过累积小的子问题的信息来解决大的问题。把子问题的解都记录下来，这样就只需对它求解一次。为此，把所有了问题编成一张表，当录下来，这样就只需对它求解一次。为此，把所有了问题编成一张表，当碰到它们时，把它们的解系统地填入表格。碰到它们时，把它们的解系统地填入表格。在本例中，考虑在本例中，考虑 G 的每一个变元是否产生的每一个变元是否产生 w 的每一个子串这样的子问题的每一个子串这样的子问题。算法把子问题的解填入一张。算法把子问题的解填入一张 nn表格。对于表格。对于 ij，表的第，表的第 (i, j) 项包含产项包含产生子串生子串

52、wi wi+1 wj 的所有变元。的所有变元。 ij 的表项没有使用。的表项没有使用。算法为算法为 w 的每一子串填写表项。首先为长为的每一子串填写表项。首先为长为 1 的子串填写表项，然后是长的子串填写表项，然后是长为为 2 的子串，依此类推。它利用短子串的表顶内容来辅助确定长子串的表的子串，依此类推。它利用短子串的表顶内容来辅助确定长子串的表项内容。项内容。41P中的问题举例-上下文无关语言 例如，假定该算法已经确定了由哪些变元产生所有长度不超过例如，假定该算法已经确定了由哪些变元产生所有长度不超过 k 的的子串。为了确定变元子串。为了确定变元 A 是否产生某一长为是否产生某一长为 k+1

53、 的子串，算法把该子串以的子串，算法把该子串以k种可能方式分裂为非空的两段。对于每一种分裂方式，算法考察每一条种可能方式分裂为非空的两段。对于每一种分裂方式，算法考察每一条规则规则 A BC ，利用以前计算的表项来确定是否，利用以前计算的表项来确定是否 B 产生第一段而且产生第一段而且 C 产产生第二段。如果生第二段。如果 B 和和 C 都产生各自的段，那么都产生各自的段，那么 A 就产生该子串，并且被就产生该子串，并且被加入相关联的表项。算法从长为加入相关联的表项。算法从长为 1 的串开始，对规则的串开始，对规则 A b 考察表格。考察表格。 42P中的问题举例-上下文无关语言证明：证明：令

54、令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是子串的起始位置是子串

55、的起始位置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）中，则）中，则接受接受；否则；否则拒绝拒绝。”43P中的问题举例-上下文无关语言 现在分析现在分析D。每一步很容易在多项式时间内运行。步骤。每一步很容易在多项式时间内运行。步骤4和和5最多运行最多运行nv次，其中次，其中v是是G中的变元数，是与中的变元

56、数，是与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 和小和小

57、 o 记法、分析算法、模型间的复杂性关系记法、分析算法、模型间的复杂性关系7.2 P类类多项式时间、多项式时间、P 中的问题举例中的问题举例7.3 NP类类NP中的问题举例、中的问题举例、P 与与 NP 问题问题7.4 NP完全性完全性多项式时间可归约性、多项式时间可归约性、NP 完全性的定义、库克完全性的定义、库克-列文定理列文定理7.5 几个几个NP完全问题完全问题顶点覆盖问题、哈密顿路径问题、子集和问题顶点覆盖问题、哈密顿路径问题、子集和问题45NP 类q 许多问题可以避免使用蛮力搜索而获得多项式时间解法。许多问题可以避免使用蛮力搜索而获得多项式时间解法。但是，在某些其它问题中，包括许多

58、有趣而有用的问题，但是，在某些其它问题中，包括许多有趣而有用的问题，避免蛮力搜索的努力还没有成功，求解它们的多项式时间避免蛮力搜索的努力还没有成功，求解它们的多项式时间算法还没有找到。算法还没有找到。q 可能这些问题具有未知原理的多项式时间算法，但至今还可能这些问题具有未知原理的多项式时间算法，但至今还没有被发现，或者它们中的某些问题就是不能在多项式时没有被发现，或者它们中的某些问题就是不能在多项式时间内解决，它们可能是间内解决，它们可能是固有地难计算固有地难计算的。的。q 一个不寻常的发现是，一个不寻常的发现是，许多问题的复杂性是联系在一起的许多问题的复杂性是联系在一起的。发现其中一个问题的

59、多项式时间算法可以用来解决整个一发现其中一个问题的多项式时间算法可以用来解决整个一类问题类问题。46多项式可验证性q 许多事情许多事情, 猜出困难，验证易。猜出困难，验证易。q 例如，解方程例如，解方程 x10+2x+7=1035q 解方程难，解方程难，验算验算根根x=2容易容易。q HAMPATH = G,s,t | G 是包含从是包含从 s 到到 t 的哈密顿路径的有向图的哈密顿路径的有向图容易获得指数时间算法，但不知是否能在多项式时间内求解。容易获得指数时间算法，但不知是否能在多项式时间内求解。该问题有一个特点，称为该问题有一个特点，称为多项式可验证性多项式可验证性。虽然还不知道一种虽然

60、还不知道一种快速（即多项式时间）快速（即多项式时间）的方法来确定图中是否包含哈的方法来确定图中是否包含哈密顿路径，但是如果密顿路径，但是如果以某种方式（可能是指数时间算法）以某种方式（可能是指数时间算法）找到这样的路找到这样的路径，就可以相信它的存在。即：径，就可以相信它的存在。即：验证验证哈密顿路径的存在可能哈密顿路径的存在可能比确定比确定它的它的存在性存在性容易容易得多。得多。q COMPOSITES = x | x = pq，整数，整数 p,q1虽然不知道判断该问题的多项式时间算法，但是容易验证一个数是不是虽然不知道判断该问题的多项式时间算法，但是容易验证一个数是不是合数合数-只需要该数