Lecture11-NP完全性

1NP完全性高文宇[e-mail]2Contents•P和NP(NondeterministicPolynomialtime)•归约•NPC问题3P和NP•最短与最长路径•欧拉回路与哈密顿回路•2-CNF(Conjunctivenormalform,合取范式)可满足性和3-CNF可满足性4P和NP•P类中包含的是在多项式时间内可以解决的问题。•NP类中包含的是在多项式时间内“可验证”的问题。是指给定某一解决方案的“证书”，就能在问题输入规模的多项式时间内，验证该“证书”是正确的。•P中任何问题都属于NP，因为若某一问题属于P，则可以在不给出证书的情况下，在多项式时间内解决它。•通俗地说，如果一个问题属于NP，且与NP中的任何问题一样“难”的，则说它属于NPC类，即NP完全的（NPComplete）。5判定问题和最优化问题•Optimizationproblem•Decisionproblem•NP完全性不直接适合于最优化问题，但适用于判定问题，因为这种问题的答案是简单的“是”或“否”。6归约•Reduction•考虑一个判定问题（A），希望在多项式时间解决该问题。称某一特定问题的输入为该问题的一个实例（instance）。现在，假设另一个不同的判定问题（B），我们知道如何在多项式时间内解决它。最后，假设有一个过程，它能将A的任何实例a转换为B的、具有如下特征的某个实例b：•（1）转换操作需要多项式时间；•（2）两个实例的答案是相同的。即a的答案若是“yes”，则b的答案亦是“yes”。•称这样一种过程为多项式时间的归约算法（ReductionAlgorithm），并且，它提供了一种在多项式时间内解决问题A的方法。7NP完全性的证明•考虑一个判定问题A，若我们已知其不存在多项式时间算法。进一步假设有一个多项式时间规约，它将一个A的实例转换成B的实例，则B一定不存在多项式时间算法。•对NP完全性的证明亦是如此。8电路可满足性问题•电路可满足性问题：给定一个由“与”，“或”，“非”门组成的布尔组合电路，它是可满足电路吗？•回答：Yes/No9证明C-SAT是NP完全（1）•引理34.5：电路可满足性问题属于NP类。•证明：Circuit-SAT可在多项式验证，因此属于NP类。10证明C-SAT是NP完全（2）•证明Circuit-SAT是NP完全问题的第二部分，就是要证明该语言是NP难度的，即必须证明NP中的每一种语言，都可以在多项式时间归约为Circuit-SAT。教材上基于计算机硬件的工作机理，给出了一个简要的证明过程。•引理34.6：C-SAT问题是NP难度的。•证明：…，C-SAT至少与NP中的任何语言具有同样的难度，并且它又是属于NP的，因此它是NP完全的。•定理34.7：C-SAT问题是NP完全的。11第一个NP完全问题•电路可满足性问题（Circuitsatisfiabilityproblem）。已知一个布尔组合电路，它由And、Or、Not门组成，我们希望知道这个电路是否存在一组布尔输入，是的它的输出为1.12NP完全性的证明•引理34.8：•IfLisalanguagesuchthatL′≤PLforsomeL′∈NPC,thenLisNP-hard.Moreover,ifL∈NP,thenL∈NPC.•Inotherwords,byreducingaknownNP-completelanguageL′toL,weimplicitlyreduceeverylanguageinNPtoL.Thus,Lemma34.8givesusamethodforprovingthatalanguageLisNP-complete:•ProveL∈NP.•SelectaknownNP-completelanguageL′.•Describeanalgorithmthatcomputesafunctionfmappingeveryinstancex∈{0,1}*ofL′toaninstancef(x)ofL.•Provethatthefunctionfsatisfiesx∈L′ifandonlyiff(x)∈Lforallx∈{0,1}*.•Provethatthealgorithmcomputingfrunsinpolynomialtime.•(Steps2-5showthatLisNP-hard.)ThismethodologyofreducingfromasingleknownNP-completelanguageisfarsimplerthanthemorecomplicatedprocessofshowingdirectlyhowtoreducefromeverylanguageinNP.13公式可满足性问题•电路可满足性问题的任何实例可以在多项式时间内，归约为公式可满足性问题的一个实例。利用归纳法可以将任意布尔组合电路表示为一个布尔公式。例如对下图的布尔电路进行归约。•CIRCUIT-SAT≤PSAT•为什么仅当公式φ可满足时，电路C才是可满足的呢？因为若φ是可满足的，则φ中每个子句都取得1值，这种赋值同样使得电路中的每个门的输出取得1值，因此C也是可满足的。φ=x10∧(x4↔¬x3)∧(x5↔(x1∨x2))∧(x6↔¬x4)∧(x7↔(x1∧x2∧x4))∧(x8↔(x5∨x6))∧(x9↔(x6∨x7))∧(x10↔(x7∧x8∧x9)).143-CNF可满足性•（1）为公式构造一棵二叉语法分析树。•（2）把树看做电路，构造公式。•（3）利用真值表将公式的子句变换为析取式。•例如：φ=((x1→x2)∨¬((¬x1↔x3)∨x4))∧¬x2.φ'=y1∧(y1↔(y2∧¬x2))∧(y2↔(y3∨y4))∧(y3↔(x1→x2))∧(y4↔¬y5)∧(y5↔(y6∨x4))∧(y6↔(¬x1→x3))15思考题•34.4-1，Considerthestraightforward(nonpolynomial-time)reductionintheproofofTheorem34.9.描述一个规模为n的电路，使用这种归约方法将其转换为一个公式时，会产生出一个规模为n的指数的公式。•34.4-3，ProfessorJagger提议通过真值表技术来证明SAT≤P3-CNF-SAT（Theorem34.10）。Thatis,theprofessorproposestotakethebooleanformulaφ,formatruthtableforitsvariables,derivefromthetruthtableaformulain3-DNFthatisequivalentto¬φ,andthennegateandapplyDeMorgan‘slawstoproducea3-CNFformulaequivalenttoφ.请指出这种策略不能产生多项式时间归约。•34.4-5，3-CNF是NP完全的，3-DNF呢？（析取范式）16广泛存在的NP完全问题•NP-completeproblemsariseindiversedomains:booleanlogic,graphs,arithmetic,networkdesign,setsandpartitions,storageandretrieval,sequencingandscheduling,mathematicalprogramming,algebraandnumbertheory,gamesandpuzzles,automataandlanguagetheory,programoptimization,biology,chemistry,physics,andmore.17NP完全问题•团（Clique）•点覆盖（VetexCover）•哈密顿回路•旅行商问题（Traveling-salesmanproblem）•子集和问题（Subset-sumproblem）18团问题•无向图G=(V,E)中的团Clique是一个节点集V‘⊆V其中每一对节点间都有边相连。即团是图G的一个完全子图。团问题是寻找图中的最大团。其判定问题是：在给定图中是否存在一个规模为k的团。•一个朴素的算法就是列出V的所有k-子集然后检验它们是否构成团。其时间复杂度为?若k为常数，则它是多项式时间，但k可能接近|V|/2，这样一来算法的运行时间就是超多项式时间，因此，人们猜想团问题不大可能存在有效算法。19定理34.11•定理34.11：团问题是NP完全的。•证明：•（1）团问题显然是多项式可验证的。•（2）从3-CNF-SAT开始归约。设φ=C1∧C2∧···∧Ck是一个具有k个子句的3-CNF布尔公式。我们根据公式φ构造一个图G。•图G=(V,E)构造如下，对φ中每个子句Cr=(l1Vl2Vl3)，将3个顶点v1、v2、v3放入V中。若一些两个条件同时满足，则用一条边连接两个顶点vi和j。•vi和vj处于不同的三元组中，即r≠s；•它们的相应文字是一致的，即li不是lj的非。•Thisgraphcaneasilybecomputedfromφinpolynomialtime.Asanexampleofthisconstruction,ifwehave•φ=(x1∨¬x2∨¬x3)∧(¬x1∨x2∨x3)∧(x1∨x2∨x3),•thenGisthegraphshowninFigure34.14.20定理34.11•定理34.11：团问题是NP完全的。•φ=(x1∨¬x2∨¬x3)∧(¬x1∨x2∨x3)∧(x1∨x2∨x3)21点覆盖•无向图G=(V,E)的点覆盖是一个节点集V’⊆V，满足若(u,v)∈E，则u∈V’或v∈V’。例如Figure34.15(b)hasavertexcover{w,z}ofsize2.22定理34.12•定理34.12：点覆盖问题是NP完全的。•证明：•定义补图如下：图G的补图就是G’是包含不在G中的那些边的图。Figure34.15展示了图G和它的补图G’。23定理34.12•归约：图G有一个大小为k的团，当且仅当其补图G’有一个大小为|V|-k的点覆盖。•证明：假设G包含一个团V’⊆V，且|V’|=k。我们可以断言V-V’是G’的一个点覆盖。设(u,v)是E’中的任意边。则(u,v)∉E,这意味着u或v至少有一个不属于团V’，因为V’中的每一对节点间都有一条E中的边相连，等价地，u或v中至少有一个属于V-V’此即边(u,v)被V-V’所覆盖。由于(u,v)是从E’中任选的边，因此E’被V-V’所覆盖。•Conversely,supposethatG’hasavertexcoverV'⊆V,where|V'|=|V|-k.Then,forallu,v∈V,if(u,v)∈Ē,thenu∈V'orv∈V'orboth.Thecontrapositiveofthisimplicationisthatforallu,v∈V,ifu∉V'andv∉V',then(u,v)E.Inotherwords,V-V'isaclique,andithassize|V|-|V'|=k.24独立集问题•独立集问题：设G=(V,E)是一个简单无向图，S是V的子集，若S中的节点在图G中都无边相连，则称S是一个独立集。25点覆盖和独立集•定理：设G=(V,E)是一个图，S是V的子集，那么S是一个独立集，当且仅当它的补V-S是一个点覆盖。•证明：•（1）若S是一个独立集。考虑任意一条边e=(u,v)。因为S是独立集，所以u和v不可能都在S中，因而u和v必有一个在V-S中，得证每一条边至少有一个端点在V-S中，所以V-S是一个点覆盖。•（2）反之，若V-S是一个点覆盖，考虑S中的任意两个节点u和v，如果它们之间有一条边e，那么e的两个端点都不在V-S中，与假设V-S是点覆盖相矛盾。因此，S中的任意两个节点之间都没有边，从而S是独立集。26点覆盖和独立集•推论：设G=(