计算理论计算复杂性2016ppt课件.pptx

《计算理论计算复杂性2016ppt课件.pptx》由会员分享，可在线阅读，更多相关《计算理论计算复杂性2016ppt课件.pptx（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、教材教材:1王王 王晓东王晓东,计算机算法设计与分析计算机算法设计与分析(第第4版版),电子工业电子工业.2S 唐常杰等译唐常杰等译,Sipser著著,计算理论导引计算理论导引,机械工业机械工业.参考资料参考资料:3C 潘金贵等译潘金贵等译,Cormen等著等著,算法导论算法导论,机械工业机械工业.4M 黄林鹏等译黄林鹏等译,Manber著著,算法引论算法引论-一种创造性方法一种创造性方法,电子电子.5刘刘 刘汝佳等刘汝佳等,算法艺术与信息学竞赛算法艺术与信息学竞赛,清华大学清华大学.6L Lewis等著等著,计算理论基础计算理论基础,清华大学清华大学.计算理论与计算理论与算法分析设计算法分析

2、设计 刘刘 庆庆 晖晖 计算理论计算理论 第三部分第三部分 计算复杂性计算复杂性 第第7章章 时间复杂性时间复杂性1.时间复杂性时间复杂性 0k1k|k 0 的时间复杂性分析的时间复杂性分析 2.不同模型的运行时间比较不同模型的运行时间比较 单带与多带单带与多带 确定与非确定确定与非确定 3.P类与类与NP类类4.NP完全性及完全性及NP完全问题完全问题一一.时间复杂度时间复杂度 时间复杂度定义时间复杂度定义 0k1k|k 0 的时间复杂度分析的时间复杂度分析 时间复杂性时间复杂性 判定器判定器M的的运行时间运行时间或或时间复杂度时间复杂度是是f:NN,f(n)是是M在在所有长为所有长为n的输

3、入的输入上运行的最大步数上运行的最大步数.若若f(n)是是M的运行时间的运行时间,则称则称 M在时间在时间f(n)内运行内运行 或或 M是是f(n)时间图灵机时间图灵机举例举例:大大O与小与小o记法记法对于函数对于函数f,g:NR+,记记f(n)=O(g(n),若存在若存在c0使得使得 记记f(n)=o(g(n),若若 分析算法分析算法讨论语言讨论语言A=0k1k|k 0 的复杂性的复杂性:M1=“对输入串对输入串w:1)扫描带扫描带,如果在如果在1的右边发现的右边发现0,则拒绝则拒绝.2)如果如果0和和1都在带上都在带上,就重复下一步就重复下一步.3)扫描带扫描带,删除一个删除一个0和一个和

4、一个1.4)如果带上同时没有如果带上同时没有0和和1,就接受就接受.”时间分析时间分析:(1)2n=O(n),4)n=O(n),(2)2n=O(n)+(3)2n=O(n)(n/2)=O(n2)所以所以M1的运行时间是的运行时间是O(n2).时间复杂性类时间复杂性类定义定义:对于函数对于函数t:NN,时间复杂性类时间复杂性类 TIME(t(n)定义为定义为:TIME(t(n)=L|存在存在O(t(n)时间时间TM判定判定L 因为因为M1是时间是时间O(n2)图灵机图灵机,所以所以A=0k1k:k 0 TIME(n2).是否存在更快的是否存在更快的TM判定判定A呢呢?图灵机图灵机M2M2=“对输入

5、串对输入串w:1)扫描带扫描带,若若1的右边有的右边有0,则拒绝则拒绝.2)若若0,1都在带上都在带上,重复以下步骤重复以下步骤.3)检查带上检查带上0,1总数的奇偶性总数的奇偶性,若是奇数若是奇数,就拒绝就拒绝.4)再次扫描带再次扫描带,第第1个个0开始开始,隔隔1个个0删除删除1个个0;第第1个个1开始开始,隔隔1个个1删除删除1个个1.5)若带上若带上同时没有同时没有0和和1,则接受则接受.否则拒绝否则拒绝.”O(n)O(n)O(n)O(n)O(n)log n总时间总时间:O(nlogn)0k1k|k 0 TIME(nlogn)由图灵机由图灵机M2知道知道A TIME(n log n)有

6、没有有没有更快的图灵机识别更快的图灵机识别A?对于对于单带单带确定图灵机确定图灵机,由由定理定理:时间时间o(nlogn)的单带图灵机判定的语言的单带图灵机判定的语言 是正则语言是正则语言.TIME(o(nlogn)正则语言类正则语言类 TIME(n)正则语言类正则语言类=TIME(n)=TIME(o(nlogn)非正则语言非正则语言 0k1k|k 0 TIME(o(nlogn)二二.不同模型的时间复杂度比较不同模型的时间复杂度比较 单带与多带单带与多带 确定与非确定确定与非确定 单带与多带运行时间比较单带与多带运行时间比较 0k1k|k 0 有有O(n)时间双带图灵机时间双带图灵机 M3=“

7、对输入串对输入串w:1)扫描扫描1带带,如果在如果在1的右边发现的右边发现0,则拒绝则拒绝.2)将将1带的带的1复制到复制到2带上带上.3)每删除一个每删除一个1带的带的0就删除一个就删除一个2带的带的1.4)如果两带如果两带上同时没有上同时没有0和和1,就接受就接受.”定理定理:设函数设函数t(n)n,则每个则每个t(n)时间多带时间多带TM 和某个和某个O(t2(n)时间单带时间单带TM等价等价.0k1k|k 0的的O(n)时间双带图灵机时间双带图灵机q0q1qaq2NTM的运行时间的运行时间定义定义:对非确定型判定器对非确定型判定器N,其运行时间其运行时间f(n)是是 在在所有所有长为长

8、为n的输入上的输入上,所有所有分支的最大步数分支的最大步数.f(n)接受接受/拒绝拒绝.f(n).TMNTM定理定理:设设t(n)n,则每个则每个 时间时间t(n)NTM都有一等价的都有一等价的 时间时间2O(t(n)TM.NTIME(t(n)TIME(2O(t(n)三三.P与与NP 多项式时间多项式时间运行时间相差多项式可以认为是小的运行时间相差多项式可以认为是小的 相差指数可以认为是大的相差指数可以认为是大的.例如例如:n3与与2n,对于对于n=1000.有关有关素性测试素性测试:Prime=p|p是素数是素数 如何编码如何编码?一进制一进制,二进制二进制,十进制十进制?典型的指数时间算法

9、来源于典型的指数时间算法来源于蛮力搜索蛮力搜索.有时通过深入理解问题可以避免蛮搜有时通过深入理解问题可以避免蛮搜.2001年年Prime被证明存在被证明存在多项式时间算法多项式时间算法.P类类定义定义:P是是单带确定单带确定TM在在 多项式时间内可判定的问题多项式时间内可判定的问题,即即 P=k TIME(nk)P类的重要性在于类的重要性在于:1)对于所有与单带确定对于所有与单带确定TM等价的等价的模型模型,P不变不变.2)P大致对应于在计算机上大致对应于在计算机上实际可解实际可解的问题的问题.研究的核心是一个问题是否属于研究的核心是一个问题是否属于P类类.NP类类NTIME(t(n)=L|L

10、可被可被O(t(n)时间时间NTM判定判定.定义定义:NP是是单带非确定单带非确定TM在在 多项式时间内可判定的问题多项式时间内可判定的问题,即即 NP=k NTIME(nk)EXP=k TIME(2(nk)P NP EXP P EXP 一些一些P问题问题有些问题初看起来不属于有些问题初看起来不属于P求最大公因子求最大公因子:欧几里德算法欧几里德算法,辗转相除法辗转相除法模模p指数运算指数运算ab mod p素性测试素性测试 等等等等以增加空间复杂性来减小时间复杂性以增加空间复杂性来减小时间复杂性 上下文无关上下文无关语言语言 有有O(n3)判定器判定器 快速验证快速验证HP=|G是包含从是包

11、含从s到到t的的 哈密顿路径哈密顿路径的有向图的有向图CLIQUE=|G是有是有k团的无向图团的无向图目前目前没有快速算法没有快速算法,但其但其成员成员是可以快速验证的是可以快速验证的.注意注意:HP的的补补可能可能不是可以快速验证的不是可以快速验证的.快速验证的特点快速验证的特点:1.只需要对语言中的串能快速验证只需要对语言中的串能快速验证.2.验证需要借助额外的信息验证需要借助额外的信息:证书证书,身份证身份证.NP问题问题团团:无向图的完全子图无向图的完全子图(所有节点都有边相连所有节点都有边相连).CLIQUE=|G是有是有k团的无向图团的无向图定理定理:CLIQUE NP.N=“对于

12、对于输入输入,这里这里G是一个图是一个图:1)非确定地选择非确定地选择G中中k个节点的子集个节点的子集c.2)检查检查G是否包含连接是否包含连接c中节点的所有边中节点的所有边.3)若是若是,则接受则接受;否则否则,拒绝拒绝.”哈密顿路径问题哈密顿路径问题HP NPHP=|G是包含从是包含从s到到t的的 哈密顿路径哈密顿路径的有向图的有向图P时间内判定时间内判定HP的的NTM:N1=“对于输入对于输入:1)非确定地选非确定地选G的所有节点的排列的所有节点的排列p1,pm.2)若若s=p1,t=pm,且对每个且对每个i,(pi,pi+1)是是G的边的边,则接受则接受;否则拒绝否则拒绝.”P与与NP

13、 P=成员资格可以成员资格可以快速快速判定判定的语言类的语言类.NP=成员资格可以成员资格可以快速快速验证验证的语言类的语言类.显然有显然有 P NP但是否有但是否有 P=NP?看起来难以想象看起来难以想象,但是现在没有发现反例但是现在没有发现反例.PNPP=NP当代数学与当代数学与理论计算机理论计算机共同的难题共同的难题.NP完全性的定义完全性的定义 SAT是是NP完全问题完全问题 一些一些NP完全问题完全问题NP完全性完全性Cook和和Levin于于70s证明证明NP中中某些问题某些问题的复杂性与的复杂性与 整个整个NP类类的复杂性相关联的复杂性相关联,即即:若这些问题中的任一个找到若这些

14、问题中的任一个找到P时间算法时间算法,则则P=NP.这些问题称为这些问题称为NP完全问题完全问题.理论意义理论意义:两方面两方面1)研究研究P与与NP关系可以只关注于一个问题的算法关系可以只关注于一个问题的算法.2)可由此说明一个可由此说明一个问题目前还没有问题目前还没有快速算法快速算法.合取范式合取范式 布尔变量布尔变量:取值为取值为1和和0(T,F)的变量的变量.布尔运算布尔运算:AND(),OR(),NOT().布尔公式布尔公式.例例:1=(x)y)(x (z),2=(x)x 称称 可满足可满足,若存在布尔变量的若存在布尔变量的0,1赋值使得赋值使得=1.不可满足不可满足 永真永真 合取

15、范式合取范式:正负文字正负文字(变量变量,变量的非变量的非)子句子句(文字的或文字的或)(x1)x2(x3)(x2(x3)x4 x5)(x4)x5)合取范式合取范式cnf(conjunctive normal form)3cnf:每个子句文字数不大于每个子句文字数不大于3,2cnf:每个子句文字数不每个子句文字数不大于大于2 可满足问题可满足问题SAT 可满足性问题可满足性问题:SAT=|是可满足是可满足的布尔公式的布尔公式 二元可满足性问题二元可满足性问题:2SAT=|是可满足的是可满足的2cnf 三元可满足性问题三元可满足性问题:3SAT=|是可满足的是可满足的3cnf 二元可满足问题二元

16、可满足问题2SAT P1.当当2cnf中有子句是单文字中有子句是单文字x,则反复执行则反复执行清洗清洗 1.1 由由x赋值赋值,1.2 删去含删去含x的子句的子句,1.3 删去含删去含 x的文字的文字 若清洗过程出现相反单文子子句若清洗过程出现相反单文子子句,则清洗则清洗失败并结束失败并结束(x1 x2)(x3x2)(x1)(x1 x2)(x3 x4)(x3 x5)(x4x5)(x3 x4)(x3x2)(x2)(x3 x4)(x3 x5)(x4x5)(x3 x4)(x3 x4)(x3 x5)(x4x5)(x3 x4)2.若无单文字子句若无单文字子句,则任选变量赋真则任选变量赋真/假值各清洗一次

17、假值各清洗一次 若两次都清洗失败若两次都清洗失败,则回答不可满足则回答不可满足.x3:(x5)(x4x5)(x4)(x4)(x4)失败失败 x3:(x4)(x4x5)(x5)成功成功3.若成功清洗后有子句剩下若成功清洗后有子句剩下,则则继续继续2.否则否则,回答可满足回答可满足.注注:见见S习题习题7.23,作者给出的答案与清洗算法作者给出的答案与清洗算法等价等价多项式时间映射归约与多项式时间映射归约与C-L定理定理 Cook-Levin定理定理:SAT P P=NP.定义定义:多项式时间多项式时间可计算函数可计算函数f:*.定义定义:称称A可可多项式时间多项式时间映射归约映射归约到到B(A

18、PB),若存在若存在多项式时间多项式时间可计算函数可计算函数f:*,w*,w A f(w)B.函数函数f称为称为A到到B的的多项式时间多项式时间归约归约.通俗地说通俗地说:f 将将A的实例编码转换为的实例编码转换为B的实例编码的实例编码.Cook-Levin定理定理:对任意对任意A NP都有都有A P SAT.定理定理1:若若 A P B,且且 B P,则则 A P.注注:定理定理1说明说明,若若SAT P,则则 NP=P.多项式时间映射归约的作用多项式时间映射归约的作用 输入输入w f f(w)M y/n w*,w A f(w)B.定理定理1:若若 A P B,且且 B P,则则 A P.证

19、明证明:设设 f:*是是A到到B的的P时间归约时间归约,B有有P时间判定器时间判定器M,则则 N=“输入输入w,计算计算M(f(w),输出输出M的运行结果的运行结果”在多项式时间内判定在多项式时间内判定A.利用利用f和和B的判定的判定器器 构造构造A的判定器的判定器 定理定理:3SAT P CLIQUE3SAT=|是可满足的是可满足的3cnf公式公式 CLIQUE=|G是有是有k团的无向图团的无向图.证明证明:设设=(a1 b1 c1)(ak bk ck),有有k个子句个子句.f()=,G有有k组节点组节点,每组每组3个个;同组同组节点无边相连节点无边相连,相反标记相反标记无边相连无边相连.f

20、(x1 x1 x2)(x1 x2 x2)(x1 x2 x2)=x1 x1 x2 x1 x2 x2 x1 x2 x2 需证需证:3SAT (G,k)CLIQUE ,3SATf()CLIQUE ()3SAT 变量赋值变量赋值(x1=0,x2=1)使得使得=1 k团团(每组挑一个真顶点得到每组挑一个真顶点得到k团团,非同组非相反非同组非相反)f()()CLIQUE.x1 x1 x2 x1 x2 x2 x1 x2 x2 NP完全性完全性 定义定义:语言语言B称为称为NP完全的完全的(NPC),若它满足若它满足:1)B NP;2)A NP,都有都有A PB.定理定理1:若若 A P B,且且 B P,则

21、则 A P.定理定理2:若若B是是NPC,且且B P,则则P=NP.定理定理3:若若B是是NPC,B PC,且且C NP,则则C是是NPC.证明证明:A NP,(A P B)+(B P C)A P C Cook-Levin定理定理:SAT是是NP完全问题完全问题.推论推论:CLIQUE是是NPC.输入输入w f f(w)M y/n w*,w A f(w)B.利用利用f和和B的判定的判定器器 构造构造A的判定器的判定器 Cook-Levin定理的证明步骤定理的证明步骤 定义定义:语言语言B称为称为NP完全的完全的(NPC),若它满足若它满足:1)B NP;2)A NP,都有都有A PB.Cook

22、-Levin定理定理:SAT是是NP完全问题完全问题.证明步骤证明步骤:1.SAT NP(?),2.A NP,A P SAT(?)N=“对于输入对于输入,是一个布尔公式是一个布尔公式:1)非确定地非确定地选择选择 所有变量的赋值所有变量的赋值T.2)检查在赋值检查在赋值T下是否下是否 =1 3)若是若是,则接受则接受;否则否则,拒绝拒绝.”SAT是是NP完全问题完全问题 要证明要证明:1)SAT NP.2)A NP,都有都有 A P SAT.思想思想:将字符串对应到布尔公式将字符串对应到布尔公式 利用接受的形式定义利用接受的形式定义.过程过程:任取任取A NP,设设N是是A的的nk时间时间NT

23、M.w(|w|=n),N接受接受w N有长度小于有长度小于nk的接受格局序列的接受格局序列 能填好能填好N在在w上的上的画面画面(一个一个nk nk表格表格)f(w)可满足可满足 结论结论:SAT是是NP完全的完全的N接受接受w能填好能填好N在在w上的画面上的画面#q0w0w1wn#nk nk 起始格局起始格局 第第2个格局个格局 第第nk个格局个格局 窗口窗口 能填好画面能填好画面:第一行是起始格局第一行是起始格局 上一行能产生上一行能产生(或等于或等于)下一行下一行 画面中有接受状态画面中有接受状态构造布尔公式构造布尔公式f(w)能能填好画面填好画面f(w)可满足可满足 f(w)=,=ce

24、llstartmoveaccept.对于任意赋值对于任意赋值:1.cell=1 每格有且只有每格有且只有一个符号一个符号;2.start=1 第一行是起始格局第一行是起始格局;3.accept=1 表格中有接受状态表格中有接受状态;4.move=1 每行由上一行格局每行由上一行格局产生产生.w,w A SAT 即即 A m SAT 若若|是是|w|的多项式的多项式,则有则有A P SAT构造构造 cell 长长O(n2k)cell=1 每格有且只有每格有且只有一个符号一个符号;的变量的变量:xi,j,s,i,j=1,nk,s Q#xi,j,s:第第i行第行第j列是否填了符号列是否填了符号s构造

25、构造 start 长长O(nk)start=1 第一行是起始格局第一行是起始格局;构造构造 accept 长长O(n2k)accept=1 表格中有接受状态表格中有接受状态 构造构造 move =cellstartmove accept.move确定表的每行是上一行的合法结果确定表的每行是上一行的合法结果.只需判断每个只需判断每个2 3窗口是否窗口是否“合法合法”.合法窗口合法窗口设设(q1,b)=(q2,c,L),(q2,e,R),a,d,s,t是任意符号是任意符号,则则aq1bq2acaq1baeq2daq1daeasbasbstastq2bsacsaabtastaq1baaq1aq1bq

26、1aq1合法合法 窗口窗口 非法非法 窗口窗口 长长O(n2k)A PSAT,SAT是是NPCf(w)=w A SAT,|=O(n2k)=cellstartmoveaccept.推论推论:3SAT是是NP完全的完全的只需将前面的只需将前面的 改造为改造为3cnf公式公式.=cellstartmove accept.任取变量赋值任取变量赋值 a1 a2 ak=1 当且仅当当且仅当 存在新变量存在新变量z的赋值使得的赋值使得(a1 a2 ak-2 z)(z ak-1 ak)=1改造后公式长度最多是原来的改造后公式长度最多是原来的3倍倍 move的改造的改造分配律分配律(a b)c=(a c)(b

27、c)(a b)(c d)(e f)=(a c e)(a c f)设合法窗口有设合法窗口有M个个,则则 move原长度是原长度是6Mn2k,改造为改造为cnf范式后范式后,move长度是长度是6Mn2k.改造为改造为3cnf后后,长度增加常数倍长度增加常数倍.所以所以3SAT是是NP完全的完全的.恰当覆盖问题恰当覆盖问题(Exact Cover,EC)有限集有限集U,论域论域,全集全集 子集簇子集簇F=S1,S2,Sm 是否有是否有F的两两不交子簇的两两不交子簇,其并为其并为U 例例:U=1,6,F=1,3,2,3,6,1,5,2,3,4,5,6,2,4 定理定理:EC NP.证明证明:非确定选

28、择子集簇非确定选择子集簇,验证验证.定理定理:3SAT PEC.定理定理:3SAT PEC.EC=|U的子集簇的子集簇F有不交子簇并为有不交子簇并为U 对于对于3cnf公式公式,构造构造 f()=设设 有变量有变量x1,xn,子句子句C1,Cs,Cj有文字有文字ajk,1 k 3 U=x1,xn C1,Cs pjk|1 j s,1 k 3 F 由下面的集合组成由下面的集合组成 变量子集变量子集 Ti,1=xi pjk|ajk=xi xi的负文字的负文字 Ti,0=xi pjk|ajk=xi xi的正文字的正文字 子句子集子句子集 Cj,pjk,文字子集文字子集 pjk 可满足可满足 (U,F)

29、有恰当覆盖有恰当覆盖 原则原则:子句子集对应真文字子句子集对应真文字,变量子集对应假文字变量子集对应假文字,文字子集补齐文字子集补齐 到到(U,F)归约举例归约举例 EC=|U的子集簇的子集簇F有不交子簇并为有不交子簇并为U 设设C1=(x1x2),C2=(x1 x2 x3),C3=(x2),C4=(x2x3),则则U=x1,x2,x3 C1,C2,C3,C4 p11,p12,p21,p22,p23,p31,p41,p42 F由下面的集合组成由下面的集合组成 变量子集变量子集 T1,1=x1,p21,T1,0=x1,p11,T2,1=x2,p12,p41,T2,0=x2,p22,p31,T3,

30、1=x3,p42,T3,0=x3,p23,子句子集子句子集 C1,p11,C1,p12,C4,p41,C4,p42,文字子集文字子集 p11,p12,p41,p42,原则原则:子句子集对应真文字子句子集对应真文字,变量子集对应假文字变量子集对应假文字,文字子集补齐文字子集补齐 哈密顿路径哈密顿路径(HP)是是NPC(3SAT PHP)HP=|G是有向图是有向图,有从有从s到到t的哈密顿路径的哈密顿路径 任任取取3cnf公式公式 =(a1 b1 d1)(ak bk dk),不妨设有不妨设有k个子句个子句c1,ck,n个变量个变量x1,xn,构造构造 f()=使得使得 可满足可满足 G有从有从s到

31、到t的的HP一般从一般从3cnf公式构造图有公式构造图有 变量构件变量构件,子句构件子句构件,联接联接构件构件变量构件和子句构件变量构件和子句构件变量变量xi表示为一个钻石结构表示为一个钻石结构xicj子句子句cj表示为一个节点表示为一个节点图图G的总体结构的总体结构对应对应n个变量个变量x1,xn,k个子句个子句c1,ck,起点起点s,终点终点t st钻石构件中的水平节点钻石构件中的水平节点分分隔隔节节点点xi分分隔隔节节点点c1c2水平行除两端的两个节点外有水平行除两端的两个节点外有3k+1个节点个节点每个子句对应一对节点每个子句对应一对节点(共共2k个个)用分隔节点隔开用分隔节点隔开(k

32、+1个个)变量与子句构件的连接变量与子句构件的连接xi分分隔隔节节点点cj当子句当子句cj含有文字含有文字xi时时添加的边添加的边当子句当子句cj含有文字含有文字 xi时时添加的边添加的边cjxi分分隔隔节节点点cjcj 可满足可满足 G有从有从s到到t的哈密顿路径的哈密顿路径 设计思路设计思路:变量赋值变量赋值1对应左对应左-右式通过钻石右式通过钻石,反之右左反之右左式式 cj可选一真文字处进出一次可选一真文字处进出一次正规路径正规路径xi分分隔隔节节点点cj当子句当子句cj含有文字含有文字xi时时添加的边添加的边当子句当子句cj含有文字含有文字 xi时时添加的边添加的边cjxi分分隔隔节节

33、点点cjcjG有从有从s到到t的哈密顿路径的哈密顿路径 可满足可满足若每个钻石都是左右式或右左式通过若每个钻石都是左右式或右左式通过,则称为正规路径则称为正规路径若若s到到t的哈密顿路径是正规路径的哈密顿路径是正规路径,则公式则公式 可满足可满足从从s到到t哈密顿哈密顿路径只能是正规路径路径只能是正规路径若非正规路径若非正规路径,如图如图,则则a2或或a3是分隔节点是分隔节点 若若a2是分隔节点是分隔节点:则则a2只与只与a1,a3相连相连 a1不能再次经过不能再次经过 a2有进无出有进无出 若若a3是是分隔分隔节点节点 则则a2只与只与a1,a3,cj相连相连 a1,cj不能不能再次经过再次

34、经过 a2有进无出有进无出xicjxla1a2a3无向哈密顿圈无向哈密顿圈HP=|G是是有从有从s到到t哈密顿路径的哈密顿路径的有向图有向图 UHP=|G是是有从有从s到到t哈密顿路径的无向图哈密顿路径的无向图 UHC=|G是是有哈密顿回路的有哈密顿回路的无向图无向图 证明证明:HP PUHPv2 v1 v0 v 旅行售货员问题是旅行售货员问题是NPCUHP=|G是是有从有从u到到v的的HP的无向图的无向图 TSP=|G有从有从s出发回到出发回到s总费用总费用 b的回路的回路 这里将这里将TSP修改为决定性问题修改为决定性问题 需要证明需要证明 有有HP f()TSP 设设G=(V,E),令令

35、V=V s,s V,E=E u,s,v,s 令令G=(V,V V),f(G)=G,s,w,b),b=n,定义权定义权w,记记 V=v1,vn,0-1背包背包(knapsack)问题是问题是NPCEC=|U的子集簇的子集簇F有不交子簇并为有不交子簇并为U KS=|K等于等于A中一些数的和中一些数的和 需要证明需要证明(U,F)有恰当覆盖有恰当覆盖 f(U,F)=(A,K)KS 举例说明举例说明:设设F有有m-1个元素个元素,则使用则使用m进制表示数进制表示数 U=u1,u2,u3,u4,F=S1,S2,S3,S1=u3,u4,S2=u2,u3,u4,S3=u1,u2,K=1 1 1 1 A=a1

36、,a2,a3 a1=0 0 1 1a2=0 1 1 1 a3=1 1 0 0 U=S1 S3 a1 0 0 1 1+a3 1 1 0 0 =K 1 1 1 1计算理论总结计算理论总结计算模型计算模型 有限自动机有限自动机 非确定有限自动机非确定有限自动机 正则表达式正则表达式 正则语言正则语言 泵引理泵引理 上下文无关文法上下文无关文法 上下文无关语言上下文无关语言 泵引理泵引理 图灵机图灵机 图灵可判定语言图灵可判定语言 图灵可识别语言图灵可识别语言 可计算理论可计算理论 停机问题非图灵可判定停机问题非图灵可判定,停机问题的补不是图灵可识别停机问题的补不是图灵可识别 计算复杂性计算复杂性 P,NP,EXP,NPC