lecture11-np完全性

《lecture11-np完全性》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NP完全性高文宇gwyy@163.com1ContentsP和NP(NondeterministicPolynomialtime)归约NPC问题2P和NP最短与最长路径欧拉回路与哈密顿回路2-CNF(Conjunctivenormalform,合取范式)可满足性和3-CNF可满足性3P和NPP类中包含的是在多项式时间内可以解决的问题。NP类中包含的是在多项式时间内“可验证”的问题。是指给定某一解决方案的“证书”，就能在问题输入规模的多项式时间内，验证该“证书”是正确的。P中任何问题都属于NP，因为若某一问题属于P，则可以在不给

2、出证书的情况下，在多项式时间内解决它。通俗地说，如果一个问题属于NP，且与NP中的任何问题一样“难”的，则说它属于NPC类，即NP完全的（NPComplete）。4判定问题和最优化问题OptimizationproblemDecisionproblemNP完全性不直接适合于最优化问题，但适用于判定问题，因为这种问题的答案是简单的“是”或“否”。5归约Reduction考虑一个判定问题（A），希望在多项式时间解决该问题。称某一特定问题的输入为该问题的一个实例（instance）。现在，假设另一个不同的判定问题（B），我们知道如何

3、在多项式时间内解决它。最后，假设有一个过程，它能将A的任何实例a转换为B的、具有如下特征的某个实例b：（1）转换操作需要多项式时间；（2）两个实例的答案是相同的。即a的答案若是“yes”，则b的答案亦是“yes”。称这样一种过程为多项式时间的归约算法（ReductionAlgorithm），并且，它提供了一种在多项式时间内解决问题A的方法。6NP完全性的证明考虑一个判定问题A，若我们已知其不存在多项式时间算法。进一步假设有一个多项式时间规约，它将一个A的实例转换成B的实例，则B一定不存在多项式时间算法。对NP完全性的证明亦是如

4、此。7电路可满足性问题电路可满足性问题：给定一个由“与”，“或”，“非”门组成的布尔组合电路，它是可满足电路吗？回答：Yes/No8证明C-SAT是NP完全（1）引理34.5：电路可满足性问题属于NP类。证明：Circuit-SAT可在多项式验证，因此属于NP类。9证明C-SAT是NP完全（2）证明Circuit-SAT是NP完全问题的第二部分，就是要证明该语言是NP难度的，即必须证明NP中的每一种语言，都可以在多项式时间归约为Circuit-SAT。教材上基于计算机硬件的工作机理，给出了一个简要的证明过程。引理34.6：C-

5、SAT问题是NP难度的。证明：…，C-SAT至少与NP中的任何语言具有同样的难度，并且它又是属于NP的，因此它是NP完全的。定理34.7：C-SAT问题是NP完全的。10第一个NP完全问题电路可满足性问题（Circuitsatisfiabilityproblem）。已知一个布尔组合电路，它由And、Or、Not门组成，我们希望知道这个电路是否存在一组布尔输入，是的它的输出为1.11NP完全性的证明引理34.8：IfLisalanguagesuchthatL′≤PLforsomeL′∈NPC,thenLisNP-hard.Mor

6、eover,ifL∈NP,thenL∈NPC.Inotherwords,byreducingaknownNP-completelanguageL′toL,weimplicitlyreduceeverylanguageinNPtoL.Thus,Lemma34.8givesusamethodforprovingthatalanguageLisNP-complete:ProveL∈NP.SelectaknownNP-completelanguageL′.Describeanalgorithmthatcomputesafunction

7、fmappingeveryinstancex∈{0,1}*ofL′toaninstancef(x)ofL.Provethatthefunctionfsatisfiesx∈L′ifandonlyiff(x)∈Lforallx∈{0,1}*.Provethatthealgorithmcomputingfrunsinpolynomialtime.(Steps2-5showthatLisNP-hard.)ThismethodologyofreducingfromasingleknownNP-completelanguageisfars

8、implerthanthemorecomplicatedprocessofshowingdirectlyhowtoreducefromeverylanguageinNP.12公式可满足性问题电路可满足性问题的任何实例可以在多项式时间内，归约为公式可满足性问题的一个实例。利用归