计算理论13NP完全

[e-mail]可计算理论2019/12/171/34Outlinefortoday•Section7.4•ProofofCook-LevinTheorem•NP-Completenessof•SATand3SAT•[e-mail]可计算理论2019/12/172/34Cook-LevinTheoremep254,cp169今天Theorems7.22,7.30&9.27:ThereareNP-completeproblems(SATand3SATforexample).Wewillhavetospendsometimeproving:“2)ForeveryANPwehaveAPSAT.”Wewillusesomeearlierworkon“puzzling”.复习Definition7.27:AlanguageBisNP-completeif:1)BisinNP,and2)ForeverylanguageANPwehaveA[e-mail]可计算理论2019/12/173/34Cook-LevinTheoremep254,cp169Theorems7.22,7.30&9.27:ThereareNP-completeproblems(SATand3SATforexample).Wewillhavetospendsometimeproving:“2)ForeveryANPwehaveAPSAT.”证明任何NP问题可在多项式时间内规约为可满足性问题“任何“二字是本定理的威力和难点，太任意了。复习Definition7.27:AlanguageBisNP-completeif:1)BisinNP,and2)ForeverylanguageANPwehaveA[e-mail]可计算理论2019/12/174/34证明思路（”任意”二字要求能刻画共性的方法）LetAbea任意的languageinNP.把A在多项式时间内规约到SAT对每w,造合取范式(CNF)w使得wAwSAT,并且从w计算w只需要poly-time换言之，LetNbethenondeterministicNPthatacceptsA.Keyidea:wAacceptingpathofNonwx1…xm[w(x1…xm)=TRUE][e-mail]可计算理论2019/12/175/34证明思路(这里，语言任意，派生路径是共性）LetAbea任意的languageinNP.把A多项式规约到SAT对每w,造合取范式(CNF)w使得wAwSAT,并且从w计算w只需要poly-time换言之，LetNbethenondeterministicNTMthatacceptsA.ourKeyidea:wAacceptingpathofNonwx1…xm[w(x1…xm)=TRUE]不确定机中有个派生路径接受w有满足合取式的指派[e-mail]可计算理论2019/12/176/34MoreProofOutline详细步骤设N是P-时间的接受A的NTM，Specificallywewillestablishthechain:wAacceptingpathofNonw派生路径x1…xm[z(x1…xm)=TRUE]合取式被满足ThereexistsasequenceC1,…,CTof格局序列configurationswith:-C1开始格局thestartconfigurationofNonw-(Cj,Cj+1)aproperNtransitionforeveryj格局转换-CTanacceptingconfiguration接受格局[e-mail]可计算理论2019/12/177/34MoreProofOutline详细步骤设N是P-时间的接受A的NTM，Specificallywewillestablishthechain:wAacceptingpathofNonw派生路径x1…xm[z(x1…xm)=TRUE]合取式被满足ThereexistsasequenceC1,…,CTof格局序列configurationswith:-C1开始格局thestartconfigurationofNonw-(Cj,Cj+1)aproperNtransitionforeveryj格局转换-CTanacceptingconfiguration接受格局[e-mail]可计算理论2019/12/178/34AcceptingPathofNonwep255,cp170C1=C2=..........CT=#q####__CELLWINDOW接受状态开始状态，当前字符，今后任务边界符当前窗口3X2与时俱进[e-mail]可计算理论2019/12/179/34SizeofPathofNonwep255cp170设N是多项式时间接受A的不确定图灵机，输入长为n时，接受路径有限长:设输入长度为n，演算步数不超过O(nk).把格局序列填入tableau（演算表格）ofnknk单元,P-time可完成填表工作单元格cell(i,j)下页用合取式w(x1…xm)描述它tableau…#q####__=[e-mail]可计算理论2019/12/1710/34HowDescribestheTableau用m个布尔变量作合取式w(x1…xm)，设法-合理描述单元，-C1是开始格局（N--NTM机，输入w）-格局转移(Cj,Cj+1)合法-CT是接受格局C1C2......CT#q####__[e-mail]可计算理论2019/12/1711/34HowDescribestheCellscp170观察：填表符号和图灵机有关联。为Q{#}，其中Q状态集,带符号集合。#为边界符技巧用单元内容定义合取式中变量如下：otherwiseFALSEsj)cell(i,ifTRUEx)s,j,i(布尔变量总数：nknk|Q{#}|完成上述构造工作用时间O(n2k)polynomialinn.正整数s=|Q{#}|[e-mail]可计算理论2019/12/1712/34复习以前讲过的函数ONE(…)合取式cp170Example:DescribeinCNFtheBooleanfunction构造一个合取式函数，当恰有一个变量为真时，函数取真，其余为假（这个函数后面有用）(单因子构件技术）otherwise0xtrueoneexactlyisthereif1)x,...,x(ONEjn1Answer:nkjkjnjjnxxxxxONE)(),...,(11至少一个为真至多一个为真需求定义构造定义V∧[e-mail]可计算理论2019/12/1713/34cellforProperCellsep255,cp170并非所有指派有意义.每单元格cell(i,j)有一个描述.对1i,jnk只有一个变量x(i,j,s)设为TRUE.符号s的个数的范围：1～c=|Q{#}|.对每单元造ONE函数（前面已经复习）把nk个单元的ONE函数全部作交运算kn1j,i)c,j,i()1,j,i(cell)x,...,x(ONE∧[e-mail]可计算理论2019/12/1714/34startfortheStartConfigurationep256#),n,1(_),1n,1(_),3n,1()w,2n,1()w,3,1()q,2,1(#),1,1(startkkn10xxxxxxx比较复杂，一个个看：图灵机N的开始状态是q0,输入串w1,…,wn.其它地方填入_表示空白和左右边界#s所以开始状态对应的公式为：它为真表示开始格局正确1行，n+2列，输入字符[e-mail]可计算理论2019/12/1715/34acceptforAcceptingep256kacceptkn1j)q,j,n(acceptx当图灵机N进入接受态qaccept时，检查表中最后一行是否包含终止状态。它对应的函数为真表示接受[e-mail]可计算理论2019/12/1716/34moveforProperTransitionsep258,cp170起止已经完成。中间格局序列C1,C2,…,CT应符合图灵机N的转移函数.局部检查所有的23窗口.这种窗口个数为(nk–1)(nk–2)下列函数取真表示全部合格#q####__2n1j1n1iovemkklegalwindow)j,i(∧[e-mail]可计算理论2019/12/1717/34LegalWindows转移窗口的检查ep257cp170窗口中无状态符，表示读写头不在此窗口，带符号应该不变。所以foralla,b,c{#}.cbacba对转移(q1,a)={(q2,b,R),(q3,c,L)}:21qbaaqacaqaqa31，，以此类推读写头右移左动[e-mail]可计算理论2019/12/1718/34MoreLegalWindowsep257,cp170读写头在全局移动，局部窗口可能看不到全部情况这些是合法的窗口:2qbacbacabqab4一旦进入接受状态后图灵机就不再变化:此窗口合法：bqabqaacceptacceptcaqcab7等等[e-mail]可计算理论2019/12/1719/34SomeIllegalWindowsep257,cp170下列窗口表明格局序列有错误，这些窗口不合法abacba124qqbqab94qcabqacaqcq#62要点：如果(q9,c,R)(q4,b)即违反了图灵机转换函数，则不合法[e-mail]可计算理论2019/12/1720/34(i,j)WindowLegal…ep258cp170L)s,...,(s)s,2j,1i()s1,j(i,)sj,(i,61621)xx(x设6格组L(Q{#})6是合法窗口集合则“(i,j)为左上角的3X2窗口合法”可以表为下列公式取真，表示所有转移正确表达:2n1j1n1iovemkklegalwindow)j,i(i上行i+1,下行∧[e-mail]可计算理论2019/12/1721/34TheCompletewFormula把上述4个条件合取:acceptmovestar