NP完全问题讲解ppt课件.ppt

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

1、NP-completeLanguagesFall20061CostasBusch-RPIPolynomialTimeReductionsPolynomialComputablefunction:suchthatforanystringcomputesinpolynomialtime:ThereisadeterministicTuringmachineFall20062CostasBusch-RPIsince,cannotusemorethantapespaceintimeObservation:Languageispolynomialtimereducibletolangua

2、geifthereisapolynomialcomputablefunctionsuchthat:Definition:Supposethatispolynomialreducibleto.Ifthen.Theorem:Proof:Machinetodecideinpolynomialtime:Oninputstring:1.ComputeLetbethemachinethatdecides2.Runoninputinpolynomialtime3.IfaccceptExampleofapolynomial-timereduction:Wewillreducethe3CNF-

3、satisfiabilityproblemtotheCLIQUEproblem3CNFformula:Eachclausehasthreeliterals3CNF-SAT={:isasatisfiable3CNFformula}Language:literalclauseA5-cliqueingraphCLIQUE={:graphcontainsa-clique}Language:Theorem:3CNF-SATispolynomialtimereducibletoCLIQUEProof:giveapolynomialtimereductionofoneproblemtoth

4、eotherTransformformulatographClause2Clause1Clause3Transformformulatograph.Example:Clause4CreateNodes:Addlinkfromaliteraltoaliteralineveryotherclause,exceptthecomplementResultingGraphTheformulaissatisfiedifandonlyiftheGraphhasa4-cliqueEndofProofWedefinetheclassofNP-completelanguagesDecidable

5、NP-completeNP-completeLanguagesNPAlanguageisNP-completeif:isinNP,andEverylanguageinNPisreducedtoinpolynomialtimeObservation:IfaNP-completelanguageisproventobeinPthen:NP-completeNPP?DecidableCook-LevinTheorem:LanguageSAT(satisfiabilityproblem)isNP-completeProof:Part2:reduceallNPlanguagestoth

6、eSATprobleminpolynomialtimePart1:SATisinNP(wehaveproventhisinpreviousclass)AnNP-completeLanguageForanystringwewillconstructinpolynomialtimeaBooleanexpressionTakeanarbitrarylanguageWewillgiveapolynomialreductionoftoSATLetbetheNonDeterministicTuringMachinethatdecidesinpolyn.timesuchthat:…………a

7、cceptacceptrejectreject(deepestleaf)depthAllcomputationsofonstring…………acceptacceptrejectreject(deepestleaf)depthConsideranacceptingcomputation…acceptinitialstateacceptstateComputationpathSequenceofConfigurationsMaximumworkingspaceareaontapeduringtimestep