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

《唐常杰翻译的计算理论导引》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、LectureNotesforComputationBook:《计算理论导引》IntroductiontotheTheoryofComputationbyMichaelSipserSection７.3多项式归约，NP问题Instructor:唐常杰TangChangjie@cs.scu.edu.cnHttp://teacher.scu.edu.cn/~chjtangStudents:Ph.D.2000---2006,SCUStyle:Lecture/Seminar2021/7/311今天课程Section7.

2、3:NPClasscp163PolynomialtimereductionsReductionfrom3SATtok-CLIQUESection7.4NP-CompletenessCook-LevinTheorem2021/7/312猜难，验易的实例许多事情,猜出困难，验证易.例如x=2,算出x10+2x+7=1035造方程易。解方程难，验算根容易。数据挖掘：安宁河断裂带拟周期110天数据挖掘：啤酒纸尿布c=0.6,s=0.052021/7/313VerifiersandNP猜—证，猜难证易，测证——验证，

3、vitrifyep243cp164LanguagesinPhavepoly-timedeciders.LanguagesinNPhavepoly-time‘verifiers’.验证机Definition7.15:AverifierforalanguageAisaprogramVsuchthatwecanwriteAasA={

4、Vacceptsforsomec}(ThestringcisthecertificatethatproveswA.)验证机—验证程序(如strcmp),c—证书(相

5、当于摇奖结果）Definition7.16:NPistheclassoflanguagesthathavepolynomialtimeverifiers.彩票中奖:猜难，证易，是NP的.2021/7/314VerifiersandNP猜—证，猜难证易，测证——验证，vitrifyep243cp164LanguagesinPhavepoly-timedeciders.判定器LanguagesinNPhavepoly-time‘verifiers’.验证器Definition7.15:Averifierfora

6、languageAisaprogramVsuchthatwecanwriteAasA={

7、Vacceptsforsomec}(ThestringcisthecertificatethatproveswA.)验证机—验证程序(如strcmp),c—证书(相当于摇奖结果）Definition7.16:NPistheclassoflanguagesthathavepolynomialtimeverifiers.彩票中奖:猜难，证易，是NP的.2021/7/315Nondeterministic

8、Poly-Timeep244cp164Theorem７.17:languageLisinNPLcanbedecidedbyapoly-timenondeter.TM.(NPNTM在P时间内判定，有些书用这性质作NP的定义Proof:LetANPhaveanO(nk)timeverifierV.ApolytimeNTMcanguesstheO(nk)certificatecthatVhastouseforxAandsimulateVon.LetNbetheO(nk)timenondet

9、er.deciderforB.TheO(nk)guessesofNdefineacertificatec.ApolytimedeterministicVcansimulateNonandverify“xB”foreverysuchx.2021/7/316NondeterministicPoly-Timeep244cp164Theorem7.17:LisNPL被NTM在P时间内判定，有些书用这性质作NP的定义Proof:[]ANPL有O(nk)时间的验证机V.就以验证机V为蓝本，.造

10、一个P时间的NTMMboolM(w){n=

11、w

12、;不确定地枚举长度为O(nk)的证书C验算式)//P时间return(V(x,c)//P时间}所以M可以基于V作出判定。即基于用P时间的验证机v,造出用P时间的判定机M下页[]长度为Nk的串只有有限个2021/7/317NondeterministicPoly-Timeep244cp164Theorem７.17:LisNPL被NTM在P时间内判定