唐常杰翻译的计算理论导引.ppt

《唐常杰翻译的计算理论导引.ppt》由会员分享，可在线阅读，更多相关《唐常杰翻译的计算理论导引.ppt（60页珍藏版）》请在装配图网上搜索。

1、2020/6/9,1/60,LectureNotesforComputation,Book:计算理论导引IntroductiontotheTheoryofComputationbyMichaelSipserSection.3多项式归约，NP问题Instructor:唐常杰TangChangjieHttp:/,2020/6/9,2/60,今天课程,Section7.3:NPClasscp163PolynomialtimereductionsReductionfrom3SATtok-CLIQUESection7.4NP-CompletenessCook-LevinTheorem,2020/6/9,

2、3/60,猜难，验易的实例,许多事情,猜出困难，验证易.例如x=2,算出x10+2x+7=1035造方程易。解方程难，验算根容易。数据挖掘：安宁河断裂带拟周期110天数据挖掘：啤酒纸尿布c=0.6,s=0.05,2020/6/9,4/60,VerifiersandNP猜证，猜难证易，测证验证，vitrifyep243cp164,LanguagesinPhavepoly-timedeciders.LanguagesinNPhavepoly-timeverifiers.验证机,Definition7.15:AverifierforalanguageAisaprogramVsuchthatwecan

3、writeAasA=|Vacceptsforsomec(ThestringcisthecertificatethatproveswA.)验证机验证程序(如strcmp),c证书(相当于摇奖结果）,Definition7.16:NPistheclassoflanguagesthathavepolynomialtimeverifiers.彩票中奖:猜难，证易，是NP的.,2020/6/9,5/60,VerifiersandNP猜证，猜难证易，测证验证，vitrifyep243cp164,LanguagesinPhavepoly-timedeciders.判定器LanguagesinNPhavepo

4、ly-timeverifiers.验证器,Definition7.15:AverifierforalanguageAisaprogramVsuchthatwecanwriteAasA=|Vacceptsforsomec(ThestringcisthecertificatethatproveswA.)验证机验证程序(如strcmp),c证书(相当于摇奖结果）,Definition7.16:NPistheclassoflanguagesthathavepolynomialtimeverifiers.彩票中奖:猜难，证易，是NP的.,2020/6/9,6/60,NondeterministicPol

5、y-Timeep244cp164,Theorem.17:languageLisinNPLcanbedecidedbyapoly-timenondeter.TM.(NPNTM在P时间内判定，有些书用这性质作NP的定义,Proof:LetANPhaveanO(nk)timeverifierV.ApolytimeNTMcanguesstheO(nk)certificatecthatVhastouseforxAandsimulateVon.LetNbetheO(nk)timenondeter.deciderforB.TheO(nk)guessesofNdefineacertificatec.Apoly

6、timedeterministicVcansimulateNonandverify“xB”foreverysuchx.,2020/6/9,7/60,NondeterministicPoly-Timeep244cp164,Theorem7.17:LisNPL被NTM在P时间内判定，有些书用这性质作NP的定义,Proof:ANPL有O(nk)时间的验证机V.就以验证机V为蓝本，.造一个P时间的NTMMboolM(w)n=|w|;不确定地枚举长度为O(nk)的证书C验算式)/P时间return(V(x,c)/P时间所以M可以基于V作出判定。即基于用P时间的验证机v,造出用P时间的判定机M下页,长度为

7、Nk的串只有有限个,2020/6/9,8/60,NondeterministicPoly-Timeep244cp164,Theorem.17:LisNPL被NTM在P时间内判定，在上页已经证明,Proof:设N是NTM,用O(nk)时间可判定L,已经知道c是证书（例如摇奖结果），检查w是否被接受（中奖）基于NTMN造出了用P时间的造验证机Vboolv(w,c)return(N();/用时为P(n).所以，基于NTMN造出了用P时间的验证机V其它书把定理当作(等价)定义：L是NP语言L是被NTM在P时间判定的语言,2020/6/9,9/60,NondeterministicPoly-Timeep

8、244cp164,Theorem7.17:LisNPL被NTM在P时间内判定，在上页已经证明,Proof:设N是NTM,用O(nk)时间可判定L,已经知道c是证书（例如摇奖结果），检查w是否被接受（中奖）造验证机Vboolv(w,c)return(N();/用时为P(n).所以，基于NTMN造出了用P时间的验证机V其它书把定理当作(等价)定义：L是NP语言L是被NTM在P时间判定的语言,2020/6/9,10/60,NondeterministicPoly-Timeep245,Corollary7.19:用NTIME(nK)表示被NTM在O(nK)时间内判定的语言族，则,通常，证书比较直观（例

9、如兑奖，strcmp即可）验证证书时只需正面验证xA，反面不必验证xA.,2020/6/9,11/60,NondeterministicPoly-Timeep245,Corollary7.19:用NTIME(nK)表示被NTM在O(nK)时间内判定的语言族，则,通常，证书比较直观（例如兑奖，strcmp即可）验证证书时只需正面验证xA，反面不必验证xA.,2020/6/9,12/60,ExampleCLIQUE(团）ep245cp165,团图中的小集团，两两有勾结的顶点集合ConsideragraphG,isthereak-clique?,4-clique,graph,butno5-cliqu

10、e,团问题CLIQUE=|graphGhasak-clique,2020/6/9,13/60,团问题cp165,CLIQUE=|graphGhasak-clique定理7.20CLIQUEinNP证明（书上第二种证明，较好理解，造NTMNBoolN()非确定地Do/用足够多CPU,并行调度选G中k个顶点，作集合c;/多项式时间ok=G中含C中两两结点之间的边;/多项式时间returnok;1个CPU在多项式时间能完成一个检查。一人买一次彩票只要多项式时间，确保得奖要指数时间,一人平均107/2次。107人并行买，一次就出大奖,2020/6/9,14/60,团问题cp160,CLIQUE=|gr

11、aphGhasak-clique定理7.20CLIQUEinNP证明（书上第二种证明，较好理解，造NTMNBoolN()非确定地Do/用足够多CPU,并行调度选G中k个顶点，作集合c;/多项式时间ok=G中含C中两两结点之间的边;/多项式时间returnok;1个CPU在多项式时间能完成一个检查。一人买一次彩票只要多项式时间，确保得奖要指数时间,一人平均107/2次。107人并行买，一次就可能出大奖,2020/6/9,15/60,团问题cp165,CLIQUE=|graphGhasak-clique如果用确定图灵机来解决。BoolDM()G中有m个定点，其中有k个顶点的子集有MK个，编码排序1

12、,2,.,MKfor(i=1;i3K-合取范式可归约为满足性等价的3-合取范式，以k=5为例用表示可满足性等价X1VX2VX3VX4VX5(X1VX2Vy1)and(y1Vx3Vy2)and(y2VX4VX5)证明左边可满足至少一个X1,.,X5为T。右边：如果X1,.,X5为F，右边变为(y1)and(y1)and(y2)and(y2)是不可满足的。所以右边可满足，至少一个X为T,此时左边也满足。,2020/6/9,26/60,ConjunctiveNormalForm合取式cp168,已经证明：每个子句中至多2变量的2-满足问题inP,是多项式时间可判定的K3K-合取范式可归约为满足性等价

13、的3-合取范式，以k=5为例用表示可满足性等价X1VX2VX3VX4VX5(X1VX2Vy1)and(y1Vx3Vy2)and(y2VX4VX5)证明左边可满足至少一个X1,.,X5为T。右边：如果X1,.,X5为F，右边变为(y1)and(y1)and(y2)and(y2)是不可满足的。所以右边可满足，至少一个X为T,此时左边也满足。,2020/6/9,27/60,ConjunctiveNormalForm合取式cp162,已经证明：每个子句中至多2变量的2-满足问题inP,是多项式时间可判定的K3K-合取范式可归约为满足性等价的3-合取范式，以k=5为例用表示可满足性等价X1VX2VX3V

14、X4VX5(X1VX2Vy1)and(y1Vx3Vy2)and(y2VX4VX5)证明(1)左边不可满足X1,.,X5全部为F,右边变为(y1)and(y1)and(y2)and(y2)不可满足。(2)右边不可满足X1,.,X5为F左边不可满足,2020/6/9,28/60,ConjunctiveNormalForm合取式cp168,所以k3的k-可满足问题等价于3满足问题3满足问题，3子句合取式是否有机会取真值3SAT=|isasatisfiable3CNFformula,2020/6/9,29/60,ACNFExample（在后面将用到的）合取式,Asacomputerscientisty

15、ouareexpectedtobefluentinBooleantransformations.,Example:DescribeinCNFtheBooleanfunction,Answer:,至少一个为真至多一个为真合成：恰有一个为真,需求定义构造定义,2020/6/9,30/60,“CLIQUESAT3SAT”复杂度等价团问题=满足问题=3满足问题,ep246,cp163-164,WewillprovethatthelanguagesCLIQUE,SATand3SATareallequallycomplexwhenmeasuredwiththepolynomialtimemeasurest

16、ick.Firstwewillprovethat3SATisnotmoredifficultthanCLIQUE:3SAT不比团问题困难于是“IfyouknowhowtosolveCLIQUEinpolytime,thenyoualsoknowhowtosolve3SATinpolytime”,2020/6/9,31/60,“CLIQUE=SAT=3SAT”复杂度等价思路：团问题=满足问题=3满足问题,ep246,cp163-164,WewillprovethatthelanguagesCLIQUE,SATand3SATareallequallycomplexwhenmeasuredwitht

17、hepolynomialtimemeasurestick.Firstwewillprovethat3SATisnotmoredifficultthanCLIQUE:先证3SAT不比团问题困难于是“IfyouknowhowtosolveCLIQUEinpolytime,thenyoualsoknowhowtosolve3SATinpolytime”,2020/6/9,32/60,MappingReducibility映射规约cp167,Thusfar,weusedreductionsinformally:If“knowinghowtosolveB”implied“knowinghowtosolv

18、eA”,thenwehadareductionfromAtoB.Herenowcomesrigor(Soundsfamiliar?),上页的描述是不严格的，不能上论文发表，需要精确化,2020/6/9,33/60,Poly-TimeFunctions多项式间函数cp167,Afunctionf:*isapoly-time-computablefunctionifthereisaTMthatoneveryinputw*haltsafterpoly(|w|)stepswithf(w)onthetape.从源到像用多项式时间p(n).N=|w|,+,-*/areallpoly-time.,Impor

19、tanthereisthatobjecttransformations,对象变换like“Givenaformula,makeagraphG”canalmostalwaysbedoneinpoly-time.这些结论要证明也不难。注意以|w|为基础，一般|W|5的时间内可以搞定。,2020/6/9,34/60,Poly-TimeFunctions多项式间函数ep249,定义7.23Afunctionf:*isapoly-time-computablefunctionifthereisaTMthatoneveryinputw*haltsafterpoly(|w|)stepswithf(w)ont

20、hetape.从源到像用多项式时间p(n).N=|w|,+,-*/areallpoly-time.,Importanthereisthatobjecttransformations,对象变换like“Givenaformula,makeagraphG”canalmostalwaysbedoneinpoly-time.这些结论要证明也不难。注意以|w|为基础，一般|W|5的时间内可以搞定算术函数的变换。,2020/6/9,35/60,PolynomialTimeReducibleep249cp167,定义7.24AlanguageAispolynomialtimereducibletoaanot

21、herlanguageBifthereisapolynomialtimecomputablefunctionf:*suchthat:wAf(w)Bforeveryw*.多项式规约：多项式时间完成源到像的变换处理,Terminology/notation:APBfisthepolynomialtimereductionofAtoBalsocalled:“polynomialtimemany-onereducible”,2020/6/9,36/60,PolynomialTimeReducibleep249cp167,Terminology/notation:APBfisthepolynomialt

22、imereductionofAtoBalsocalled:“polynomialtimemany-onereducible”,定义7.24AlanguageAispolynomialtimereducibletoaanotherlanguageBifthereisapolynomialtimecomputablefunctionf:*suchthat:wAf(w)Bforeveryw*.多项式规约：多项式时间完成源到像的变换处理,2020/6/9,37/60,PolytimeAPBcp167,A,f,f,B,补充引理IfAisinP,thenAPBforeverynontrivialB.(Le

23、t1Band0B.)多项式问题总能被多项式地规约到多于二元的集合证：AinP,有多项式判定函数:Aaccept,reject造h:accept,rejectB,再令f(x)=g(h(x),“Thefunctionfdoesallthework”,2020/6/9,38/60,PolytimeAPBcp167,A,f,f,B,补充引理IfAisinP,thenAPBforeverynontrivialB.(Let1Band0B.)多项式问题总能被多项式地规约到多于二元的集合证：AinP,有多项式判定函数:Aaccept,reject造h:accept,rejectB,再令f(x)=g(h(x),

24、“Thefunctionfdoesallthework”,2020/6/9,39/60,PobeysPOrderingP遵守P归约次序,cp167,Theorem7.25:IfAPBandBisinP,thenAisinPaswell.Proof:用C语言表达，直观boolSolve_A(x)y=f(x)/多项式时间归约，ABreturn(Solve_B(y);/多项式时间计算解决B下页是书上的证明,2020/6/9,40/60,PobeysPOrderingP遵守P归约次序,cp168,Theorem7.25:书上的证明，可略IfAPBandBisinP,thenAisinPaswell.P

25、roof:LetMbethepoly-timeTMforBandfthereducingfunctionfromAtoB.ConsidertheTM:Oninputw:1)Computef(w)2)RunMonf(w)andgivethesameoutput.Bydefinitionoff:wAifandonlyiff(w)B.M“accepts”f(w)inpoly-timeifwA,andM“rejects”f(w)inpoly-timeifwA.,2020/6/9,41/60,PobeysPOrderingP遵守P归约次序,cp185,Theorem7.25:书上的证明，可略IfAPBa

26、ndBisinP,thenAisinPaswell.Proof:LetMbethepoly-timeTMforBandfthereducingfunctionfromAtoB.ConsidertheTM:Oninputw:1)Computef(w)2)RunMonf(w)andgivethesameoutput.Bydefinitionoff:wAifandonlyiff(w)B.M“accepts”f(w)inpoly-timeifwA,andM“rejects”f(w)inpoly-timeifwA.,2020/6/9,42/60,准备完毕，回头解决“3SAT不比团问题难”,cp168,团

27、图中的小集团，两两有勾结的顶点集合政治上忌讳团ConsideragraphG,isthereak-clique?,4-clique,graph,butno5-clique,CLIQUE=|graphGhasak-clique,2020/6/9,43/60,Idea3SATPCLIQUE,对给定3CNF，造一个图（及其团问题）Turnevery3CNFformula(x1,xn)intoagraphGsuchthatthekclausesofcanbesatisfiedwithanassignment0,1nifandonlyifGhasak-clique.,2020/6/9,44/60,Exa

28、mple3SATtoCLIQUE先获取一些直观启示重要研究方法，如果观察推翻了猜想，就省了力。cp168,Formula(4clauses,4variables):4变量的3子句归约为团,由3合取范式造对应图的方法设有k个子句（这里k=4)（1）分K组画3k个顶点，（2）按子句中变量标记顶点，（3）连接不在同一组中的任意两顶点,（4）让后把矛盾的边去掉，如上述4步工作可在多项式时间内可完成即p时间映射归约,2020/6/9,45/60,3SATCLIQUE.已经完成P-时间映射归约,均True,是个满足的指派，对应顶点成为团,均True,是个不满足的指派,当公式为真时，每个3-合取范式中至少一

29、个变量为真，设红箭头所指为真,2020/6/9,46/60,3SATtoCLIQUEReduction(1)已经证明Clique是NP的，现想证明3SAT是NP,cp168,设是3字句合取式公式3CNF,G是图(在p时间内，如上页方法构造）下证公式3满足图中有k团,【公式3合取范式可满足图中有k团】设已经被满足为真,则每个3合取范式中至少一个文字为真，把它对应的顶点选出来，一共有k个，现在证明他们成为团-东南西北的3-点组中各选了一个-只把矛盾边(如x1-X1)去掉,这些选出来的顶点不会矛盾（否则总的值不会真），所以两两有连线,2020/6/9,47/60,3SATtoCLIQUEReduct

30、ion(1)已经证明Clique是NP的，先想证明3SAT是NP,cp165,设是3字句合取式公式3CNF,G是图(在p时间内，如上页方法构造）下证公式3满足图中有k团,【公式3合取范式可满足图中有k团】设已经被满足为真,则每个3合取范式中至少一个文字为真，把它对应的顶点选出来，一共有k个，现在证明他们成为团-东南西北的3-点组中各选了一个-只把矛盾边(如x1-X1)去掉,这些选出来的顶点不会矛盾（否则总的值不会真），所以两两有连线,2020/6/9,48/60,3SATtoCLIQUEReduction(2),结论:3SATGk-CLIQUE(withkthenumberofclauseso

31、f).注意:映射f:Gp-时间可计算的,证明反面【图中有k团3合取范式可满足】设图G中有k-clique,因为同组顶点无连线，团的K个顶点必然分布在东南西北的三元组中，即每个子句中选了一个文字，赋它们予真值，则每个子句为真，其合取式也为真.,2020/6/9,49/60,3SATtoCLIQUEReduction(2),结论:3SATGk-CLIQUE(withkthenumberofclausesof).注意:映射f:Gp-时间可计算的,明反面证【图中有k团公式3可满足】设图G中有k-clique,因为同组顶点无连线，团的K个顶点必然分布在东南西北的三元组中，即每个子句中选了一个文字，赋它们

32、予真值，则每个子句为真，其合取式也为真.,2020/6/9,50/60,NP-CompletenessNP-完全性ep253cp168,Definition7.27:AlanguageBisNP-completeif:1)BisinNP,and2)ForeverylanguageANPwehaveAPB.,直观：NP完全即硬NP，最难啃的NPNP-completeproblemsarethemostdifficultproblemsinNPIfweomitrequirement1),thenwesometimessaythatBisNP-hard.有类问题是软NP普通人：可用NP时间解决。专家

33、可设计DP-时间解决，如2SAT问题,2020/6/9,51/60,NP-CompletenessNP-完全性ep253cp168,Definition7.27:AlanguageBisNP-completeif:1)BisinNP,and2)ForeverylanguageANPwehaveAPB.,直观：NP完全即硬NP，最难啃的NPNP-completeproblemsarethemostdifficultproblemsinNPIfweomitrequirement1),thenwesometimessaythatBisNP-hard.有类问题是软NP普通人可用NP时间解决。专家可设计

34、算法在DP-时间解决，如2SAT问题,多项式规约,2020/6/9,52/60,Theorem7.28ep253.cp169,定理7.28IfthereisanNP-completeproblemBthatcanbedecidedindeterministicpolynomialtime,thenforalllanguagesANPwealsohaveAP.有某个聪明人用多项式时间作了一个硬NP问题，则全部NP问题都可用多项式时间作，包括彩票问题（看来不可能）,Proof:IfANP,thenbythedefinitionofNP-completeness:APB.FromBP,itfollo

35、wsthatalsoAP.,2020/6/9,53/60,Theorem7.28ep253.cp169,定理7.28IfthereisanNP-completeproblemBthatcanbedecidedindeterministicpolynomialtime,thenforalllanguagesANPwealsohaveAP.有某个聪明人用多项式时间作了一个硬NP问题，则全部NP问题都可用多项式时间作，包括彩票问题（看来不可能）,Proof:IfANP,thenbythedefinitionofNP-completeness:APB.FromBP,itfollowsthatalsoA

36、P.,2020/6/9,54/60,Theorem.28ep253.cp169,定理7.28IfthereisanNP-completeproblemBthatcanbedecidedindeterministicpolynomialtime,thenforalllanguagesANPwealsohaveAP.有某个聪明人用多项式时间作了一个硬NP问题，则全部NP问题都可用多项式时间作，包括彩票问题（看来，不可能）,Proof:IfANP,thenbythedefinitionofNP-completeness:APB.FromBP,itfollowsthatalsoAP.,2020/6/9

37、,55/60,Cook-LevinTheoremep254cp169,Theorems7.22,7.30&9.27:3SAT是NP-complete的。推论ThereareNP-completeproblems存在NP完全问题(SATand3SATforexample).,Wewillhavetospendsometimeproving:“2)ForeveryANPwehaveAPSAT.”,Wewillusesomeearlierworkon“puzzling”.欲知证明如何，且听下回分解,2020/6/9,56/60,Cook-LevinTheoremep254cp169,Theorems

38、7.22,7.30&9.27:3SAT是NP-complete的。推论ThereareNP-completeproblems存在NP完全问题(SATand3SATforexample).,Wewillhavetospendsometimeproving:“2)ForeveryANPwehaveAPSAT.”,Wewillusesomeearlierworkon“puzzling”.欲知证明如何，且听下回分解,2020/6/9,57/60,2020/6/9,58/60,2020/6/9,59/60,小结,Section7.3:NPClasscp163PolynomialtimereductionsReductionfrom3SATtok-CLIQUESection7.4NP-CompletenessCook-LevinTheorem,2020/6/9,60/60,AnyQuestion?,Thankyou!,