计算理论13NP完全ppt课件.ppt

《计算理论13NP完全ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、OutlinefortodaySection7.4ProofofCook-LevinTheoremNP-CompletenessofSATand3SATProvingNP-Completeness2021/9/31Cook-LevinTheoremep254,cp169今天Theorems7.22,7.30&9.27:ThereareNP-completeproblems(SATand3SATforexample).Wewillhavetospendsometimeproving:“2)ForeveryANPwehaveAPSAT.”Wew

2、illusesomeearlierworkon“puzzling”.复习Definition7.27:AlanguageBisNP-completeif:1)BisinNP,and2)ForeverylanguageANPwehaveAPB.2021/9/32Cook-LevinTheoremep254,cp169Theorems7.22,7.30&9.27:ThereareNP-completeproblems(SATand3SATforexample).Wewillhavetospendsometimeproving:“2)Fore

3、veryANPwehaveAPSAT.”证明任何NP问题可在多项式时间内规约为可满足性问题“任何“二字是本定理的威力和难点，太任意了。复习Definition7.27:AlanguageBisNP-completeif:1)BisinNP,and2)ForeverylanguageANPwehaveAPB.2021/9/33证明思路（”任意”二字要求能刻画共性的方法）LetAbea任意的languageinNP.把A在多项式时间内规约到SAT对每w,造合取范式(CNF)w使得wAwSAT,并且从w计算w只需要poly-

4、time换言之，LetNbethenondeterministicNPthatacceptsA.Keyidea:wAacceptingpathofNonwx1…xm[w(x1…xm)=TRUE]2021/9/34证明思路(这里，语言任意，派生路径是共性）LetAbea任意的languageinNP.把A多项式规约到SAT对每w,造合取范式(CNF)w使得wAwSAT,并且从w计算w只需要poly-time换言之，LetNbethenondeterministicNTMthatacceptsA.ourKeyid

5、ea:wAacceptingpathofNonwx1…xm[w(x1…xm)=TRUE]不确定机中有个派生路径接受w有满足合取式的指派2021/9/35MoreProofOutline详细步骤设N是P-时间的接受A的NTM，Specificallywewillestablishthechain:wAacceptingpathofNonw派生路径x1…xm[z(x1…xm)=TRUE]合取式被满足ThereexistsasequenceC1,…,CTof格局序列configurationswith:-C1开始

6、格局thestartconfigurationofNonw-(Cj,Cj+1)aproperNtransitionforeveryj格局转换-CTanacceptingconfiguration接受格局2021/9/36MoreProofOutline详细步骤设N是P-时间的接受A的NTM，Specificallywewillestablishthechain:wAacceptingpathofNonw派生路径x1…xm[z(x1…xm)=TRUE]合取式被满足ThereexistsasequenceC1,…,CTof格局序

7、列configurationswith:-C1开始格局thestartconfigurationofNonw-(Cj,Cj+1)aproperNtransitionforeveryj格局转换-CTanacceptingconfiguration接受格局2021/9/37AcceptingPathofNonwep255,cp170C1=C2=..........CT=CELLWINDOW接受状态开始状态，当前字符，今后任务边界符当前窗口3X2与时俱进2021/9/38SizeofPathofNonwep255cp170设N是多项式时间接受A的不确

8、定图灵机，输入长为n时，接受路径有限长:设输入长度为n，演算步数不超过O(nk).把格局序列填入tableau（演算表格）ofnknk单元,P-ti