计算理论-计算复杂性-2016

教材:[1][王]王晓东,计算机算法设计与分析(第4版),电子工业.[2][S]唐常杰等译,Sipser著,计算理论导引,机械工业.参考资料:[3][C]潘金贵等译,Cormen等著,算法导论,机械工业.[4][M]黄林鹏等译,Manber著,算法引论-一种创造性方法,电子.[5][刘]刘汝佳等,算法艺术与信息学竞赛,清华大学.[6][L]Lewis等著,计算理论基础,清华大学.计算理论与算法分析设计刘庆晖计算理论第三部分计算复杂性第7章时间复杂性1.时间复杂性{0k1k|k0}的时间复杂性分析2.不同模型的运行时间比较单带与多带确定与非确定3.P类与NP类4.NP完全性及NP完全问题一.时间复杂度•时间复杂度定义•{0k1k|k0}的时间复杂度分析时间复杂性•判定器M的运行时间或时间复杂度是f:NN,f(n)是M在所有长为n的输入上运行的最大步数.•若f(n)是M的运行时间,则称M在时间f(n)内运行或M是f(n)时间图灵机举例:大O与小o记法对于函数f,g:NR+,记f(n)=O(g(n),若存在c0使得cngnfn)()(lim记f(n)=o(g(n)),若0)()(limngnfn分析算法讨论语言A={0k1k|k0}的复杂性:M1=“对输入串w:1)扫描带,如果在1的右边发现0,则拒绝.2)如果0和1都在带上,就重复下一步.3)扫描带,删除一个0和一个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:NN,时间复杂性类TIME(t(n))定义为:TIME(t(n))={L|存在O(t(n))时间TM判定L}因为M1是时间O(n2)图灵机,所以A={0k1k:k0}TIME(n2).是否存在更快的TM判定A呢?图灵机M2M2=“对输入串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)logn总时间:O(nlogn){0k1k|k0}TIME(nlogn)由图灵机M2知道ATIME(nlogn)有没有更快的图灵机识别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=“对输入串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)时间双带图灵机q0q1└┘qaq2RR$00RR0└┘└┘LR1└┘LR1└┘LR$NTM的运行时间定义:对非确定型判定器N,其运行时间f(n)是在所有长为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是素数}如何编码?一进制,二进制,十进制?典型的指数时间算法来源于蛮力搜索.有时通过深入理解问题可以避免蛮搜.2001年Prime被证明存在多项式时间算法.P类定义:P是单带确定TM在多项式时间内可判定的问题,即P=kTIME(nk)P类的重要性在于:1)对于所有与单带确定TM等价的模型,P不变.2)P大致对应于在计算机上实际可解的问题.研究的核心是一个问题是否属于P类.NP类NTIME(t(n))={L|L可被O(t(n))时间NTM判定.}定义:NP是单带非确定TM在多项式时间内可判定的问题,即NP=kNTIME(nk)EXP=∪kTIME(2^(nk))PNPEXPPEXP一些P问题有些问题初看起来不属于P求最大公因子:欧几里德算法,辗转相除法模p指数运算abmodp素性测试等等以增加空间复杂性来减小时间复杂性上下文无关语言有O(n3)判定器快速验证HP={G,s,t|G是包含从s到t的哈密顿路径的有向图}CLIQUE={G,k|G是有k团的无向图}目前没有快速算法,但其成员是可以快速验证的.注意:HP的补可能不是可以快速验证的.快速验证的特点:1.只需要对语言中的串能快速验证.2.验证需要借助额外的信息:证书,身份证.NP问题团:无向图的完全子图(所有节点都有边相连).CLIQUE={G,k|G是有k团的无向图}定理:CLIQUENP.N=“对于输入G,k,这里G是一个图:1)非确定地选择G中k个节点的子集c.2)检查G是否包含连接c中节点的所有边.3)若是,则接受;否则,拒绝.”哈密顿路径问题HPNPHP={G,s,t|G是包含从s到t的哈密顿路径的有向图}P时间内判定HP的NTM:N1=“对于输入G,s,t:1)非确定地选G的所有节点的排列p1,…pm.2)若s=p1,t=pm,且对每个i,(pi,pi+1)是G的边,则接受;否则拒绝.”P与NPP=成员资格可以快速判定的语言类.NP=成员资格可以快速验证的语言类.显然有PNP但是否有P=NP?看起来难以想象,但是现在没有发现反例.PNPP=NP当代数学与理论计算机共同的难题.•NP完全性的定义•SAT是NP完全问题•一些NP完全问题NP完全性Cook和Levin于70’s证明NP中某些问题的复杂性与整个NP类的复杂性相关联,即:若这些问题中的任一个找到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.不可满足永真•合取范式:正负文字(变量,变量的非)子句(文字的或)((x1)x2(x3))(x2(x3)x4x5)((x4)x5)•合取范式cnf(conjunctivenormalform)3cnf:每个子句文字数不大于3,2cnf:每个子句文字数不大于2可满足问题SAT•可满足性问题:SAT={|是可满足的布尔公式}•二元可满足性问题:2SAT={|是可满足的2cnf}•三元可满足性问题:3SAT={|是可满足的3cnf}二元可满足问题2SATP1.当2cnf中有子句是单文字x,则反复执行清洗1.1由x赋值,1.2删去含x的子句,1.3删去含x的文字若清洗过程出现相反单文子子句,则清洗失败并结束(x1x2)(x3x2)(x1)(x1x2)(x3x4)(x3x5)(x4x5)(x3x4)(x3x2)(x2)(x3x4)(x3x5)(x4x5)(x3x4)(x3x4)(x3x5)(x4x5)(x3x4)2.若无单文字子句,则任选变量赋真/假值各清洗一次若两次都清洗失败,则回答不可满足.x3:(x5)(x4x5)(x4)(x4)(x4)失败x3:(x4)(x4x5)(x5)成功3.若成功清洗后有子句剩下,则继续2.否则,回答可满足.注:见[S]习题7.23,作者给出的答案与清洗算法等价多项式时间映射归约与C-L定理•Cook-Levin定理:SATPP=NP.•定义:多项式时间可计算函数f:**.•定义:称A可多项式时间映射归约到B(APB),若存在多项式时间可计算函数f:**,w*,wAf(w)B.函数f称为A到B的多项式时间归约.通俗地说:f将A的实例编码转换为B的实例编码.•Cook-Levin定理:对任意ANP都有APSAT.•定理1:若APB,且BP,则AP.•注:定理1说明,若SATP,则NP=P.多项式时间映射归约的作用输入wff(w)My/nw*,wAf(w)B.•定理1:若APB,且BP,则AP.证明:设f:**是A到B的P时间归约,B有P时间判定器M,则N=“输入w,计算M(f(w)),输出M的运行结果”在多项式时间内判定A.利用f和B的判定器构造A的判定器定理:3SATPCLIQUE3SAT={|是可满足的3cnf公式}CLIQUE={G,k|G是有k团的无向图}.证明:设=(a1b1c1)…(akbkck),有k个子句.f()=G,k,G有k组节点,每组3个;同组节点无边相连,相反标记无边相连.f((x1x1x2)(x1x2x2)(x1x2x2))=G,3x1x1x2x1x2x2x1x2x2需证:3SAT(G,k)CLIQUE,3SATf()CLIQUE((x1x1x2)(x1x2x2)(x1x2x2))3SAT变量赋值(x1=0,x2=1)使得=1k团(每组挑一个真顶点得到k团,非同组非相反)f()(G,3)CLIQUE.x1x1x2x1x2x2x1x2x2NP完全性•定义:语言B称为NP完全的(NPC),若它满足:1)BNP;2)ANP,都有APB.•定理1:若APB,且BP,则AP.•定理2:若B是NPC,且BP,则P=NP.•定理3:若B是NPC,BPC,且CNP,则C是NPC.证明:ANP,(APB)+(BPC)APC•Cook-Levin定理:SAT是NP完全问题.•推论:CLIQUE是NPC.输入wff(w)My/nw*,wAf(w)B.利用f和B的判定器构造A的判定器Cook-Levin定理的证明步骤•定义:语言B称为NP完全的(NPC),若它满足:1)BNP;2)ANP,都有APB.•Cook-Levin定理:SAT是NP完全问题.证明步骤:1.SATNP(?),2.ANP,APSAT(?)N=“对于输入,是一个布尔公式:1)非确定地选择所有变量的赋值T.2)检查在赋值T下是否=13)若是,则接受;否则,拒绝.”SAT是NP完全问题•要证明:1)SATNP.2)ANP,都有APSAT.•思想:将字符串对应到布尔公式利用接受的形式定义.•过程:任取ANP,设N是A的nk时间NTM.w(|w|=n),N接受wN有长度小于nk的接受格局序列能填好N在w上的画面(一个nknk表格)f(w)可满足•结论:SAT是NP完全的N接受w能填好N在w上的画面#q0w0w1…wn#####nknk起始格局第2个格局第nk个格局窗口能填好画面:第一行是起始格局上一行能产生(或等于)下一行画面中有接受状态构造布尔公式f(