计算理论12_多项式归约NP

[e-mail]可计算理论2019/12/171/60今天课程•Section7.3:NPClasscp163•Polynomialtimereductions•Reductionfrom3SATtok-CLIQUE•Section7.4NP-Completeness•[e-mail]可计算理论2019/12/172/60猜难，验易的实例许多事情,猜出困难，验证易.例如x=2,算出x10+2x+7=1035造方程易。解方程难，验算根容易。[e-mail]可计算理论2019/12/173/60VerifiersandNP猜—证，猜难证易，测证——验证，vitrifyep243cp164LanguagesinPhavepoly-timedeciders.LanguagesinNPhavepoly-time‘verifiers’.验证机Definition7.15:AverifierforalanguageAisaprogramVsuchthatwecanwriteAasA={w|Vacceptsw,cforsomec}(ThestringcisthecertificatethatproveswA.)验证机—验证程序(如strcmp),c—证书(相当于摇奖结果）Definition7.16:NPistheclassoflanguagesthathavepolynomialtimeverifiers.彩票中奖:猜难，证易，是NP的[e-mail]可计算理论2019/12/174/60VerifiersandNP猜—证，猜难证易，测证——验证，vitrifyep243cp164LanguagesinPhavepoly-timedeciders.判定器LanguagesinNPhavepoly-time‘verifiers’.验证器Definition7.15:AverifierforalanguageAisaprogramVsuchthatwecanwriteAasA={w|Vacceptsw,cforsomec}(ThestringcisthecertificatethatproveswA.)验证机—验证程序(如strcmp),c—证书(相当于摇奖结果）Definition7.16:NPistheclassoflanguagesthathavepolynomialtimeverifiers.彩票中奖:猜难，证易，是NP的[e-mail]可计算理论2019/12/175/60NondeterministicPoly-Timeep244cp164Theorem７.17:languageLisinNPLcanbedecidedbyapoly-timenondeter.TM.(NPNTM在P时间内判定，有些书用这性质作NP的定义Proof:LetANPhaveanO(nk)timeverifierV.ApolytimeNTMcanguesstheO(nk)certificatecthatVhastouseforxAandsimulateVonx,c.LetNbetheO(nk)timenondeter.deciderforB.TheO(nk)guessesofNdefineacertificatec.ApolytimedeterministicVcansimulateNonx,candverify“xB”[e-mail]可计算理论2019/12/176/60NondeterministicPoly-Timeep244cp164Theorem7.17:LisNPL被NTM在P时间内判定，有些书用这性质作NP的定义Proof:[]ANPL有O(nk)时间的验证机V.就以验证机V为蓝本，.造一个P时间的NTMMboolM(w){n=|w|;不确定地枚举长度为O(nk)的证书C验算式)//P时间return(V(w,c)//P时间}所以M可以基于V作出判定。即基于用P时间的验证机v,造出用P时间的判定机M下页[]长度为Nk的串只有有限个[e-mail]可计算理论2019/12/177/60NondeterministicPoly-Timeep244cp164Theorem７.17:LisNPL被NTM在P时间内判定，[]在上页已经证明Proof:[]设N是NTM,用O(nk)时间可判定L,已经知道c是证书（例如摇奖结果），检查w是否被接受（中奖）基于NTMN造出了用P时间的造验证机Vboolv(w,c){return(N(w,c));//用时为P(n)}.所以，基于NTMN造出了用P时间的验证机V其它书把定理当作(等价)定义：L是NP语言L是被NTM在P时间判定的语言[e-mail]可计算理论2019/12/178/60NondeterministicPoly-Timeep244cp164Theorem7.17:LisNPL被NTM在P时间内判定，[]在上页已经证明Proof:[]设N是NTM,用O(nk)时间可判定L,已经知道c是证书（例如摇奖结果），检查w是否被接受（中奖）造验证机Vboolv(w,c){return(N(x,c));//用时为P(n)}.所以，基于NTMN造出了用P时间的验证机V其它书把定理当作(等价)定义：L是NP语言L是被NTM在P时间判定的语言[e-mail]可计算理论2019/12/179/60NondeterministicPoly-Timeep245Corollary7.19:用NTIME(nK)表示被NTM在O(nK)时间内判定的语言族，则通常，证书比较直观（例如兑奖，strcmp即可）验证证书时只需正面验证xA，反面不必验证x[e-mail]可计算理论2019/12/1710/60NondeterministicPoly-Timeep245Corollary7.19:用NTIME(nK)表示被NTM在O(nK)时间内判定的语言族，则通常，证书比较直观（例如兑奖，strcmp即可）验证证书时只需正面验证xA，反面不必验证x[e-mail]可计算理论2019/12/1711/60ExampleCLIQUE(团）ep245cp165团—图中的小集团，两两有勾结的顶点集合ConsideragraphG,isthereak-clique?4-cliquegraphbutno5-clique团问题CLIQUE={G,k|graphGhasak-clique}[e-mail]可计算理论2019/12/1712/60团问题cp165CLIQUE={G,k|graphGhasak-clique}定理7.20CLIQUEinNP证明（书上第二种证明，较好理解，造NTMNBoolN(G,k){非确定地Do//用足够多CPU,并行调度{选G中k个顶点，作集合c;//多项式时间ok=G中含C中两两结点之间的边;//多项式时间returnok;}}1个CPU在多项式时间能完成一个检查。一人买一次彩票只要多项式时间，确保得奖要指数时间,一人平均107/2次。107人并行买，一次就出大奖[e-mail]可计算理论2019/12/1713/60团问题cp160CLIQUE={G,k|graphGhasak-clique}定理7.20CLIQUEinNP证明（书上第二种证明，较好理解，造NTMNBoolN(G,k){非确定地Do//用足够多CPU,并行调度{选G中k个顶点，作集合c;//多项式时间ok=G中含C中两两结点之间的边;//多项式时间returnok;}}1个CPU在多项式时间能完成一个检查。一人买一次彩票只要多项式时间，确保得奖要指数时间,一人平均107/2次。107人并行买，一次就可能出大奖[e-mail]可计算理论2019/12/1714/60团问题cp165CLIQUE={G,k|graphGhasak-clique}如果用确定图灵机来解决。BoolDM(G,k){G中有m个定点，其中有k个顶点的子集有mK个，编码排序1,2,..,mKfor(i=1;imK;i++)//按次序检查子集c{ok=C中两两结点之间的边在G中；returnok;}}说明确定机用指数时间，可以解决。但不排除某个聪明人能找到确定机P时间的方法书上的定理8.21简单，自学[e-mail]可计算理论2019/12/1715/60团问题cp165CLIQUE={G,k|graphGhasak-clique}如果用确定图灵机来解决。BoolDM(G,k){G中有m个定点，其中有k个顶点的子集有n=m!/k!*(m-k)!个，编码排序1,2,..,n.for(i=1;in;i++)//按次序检查子集c{ok=C中两两结点之间的边在G中；returnok;}}说明用确定机可在阶乘(指数)时间内解决。现在还不能排除某个聪明人能找到确定机P时间的方法（NP=P?)[e-mail]可计算理论2019/12/1716/602子集和问题，找补零钱SubsetsumSUM-SUBSET10,2,4,8SUM-SUBSET11,2,4,8…because2+8=10…because11cannotbemadeoutof{2,4,8}问题的形式化描述：t}ythatsuchSRsubsetaistherex,...,xS|tS,{SUM-SUBSETRyk1定理7.21子集和问题Subset-Sum属于NP可作为自学内容问题的直观实例(1)不找补购物(2)装背包，又称背包问题商品价格口袋中零钱[e-mail]可计算理论2019/12/1717/602子集和找补零钱Subsetsum富翁的化解方法：“不用找补了”修改t是潇洒？大方？畏难（NP-hard)？t}ythatsuchSRsubsetaistherex,...,xS|tS,{SUM-SUBSETRyk1[e-mail]可计算理论2019/12/1718/60定理7.21子集和问题简单，可考虑自学子集和问题SUBSET-SUM。在这个问题中有一个数集x1，…，xk和一个目标数t。要判定在这个集合中是否有一个加起来等于t的子集。即SUBSET-SUM＝｛s，t｜s＝｛x1，…，xk｝，且存在｛y1，…，yl｝Í｛x1，…，xk｝使得｝例如，｛4，11，16，21，27｝，25∈SUBSET-SUM，因为4＋21＝25。注意｛x1，…，xk｝和｛y1，…，yl｝被看作是多重集(multisets)，因此允许元素重复。[e-mail]可计算理论2019/12/1719/60定理7.21SUBSET-SUM属于NP。证明思路子集就是证书。证明下面是SUBSET-SUM的一个验证机V。V＝“对输入S，t，c：1）检查c是否是加起来等于t的数的集合。2）检查S是否包含c中的所有数。3）若两项检查都通过，则接受；否则，拒绝。”[e-mail]可计算理论2019/12/1720/60coNP注意这些集合的补集，~Clique和～Subse-Sum不是很明显