NP完全问题证明

几个NP完全问题什么是NP完全问题NP完全问题，是世界七大数学难题之一。NP的英文全称是Non-deterministicPolynomial的问题，即多项式复杂程度的非确定性问题。简单的写法是NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P七大数学难题这七个“千年大奖问题”是：NP完全问题、霍奇猜想、庞加莱猜想、黎曼假设、杨－米尔斯理论、纳卫尔－斯托可方程、BSD猜想千年大奖问题美国麻州的克雷（Clay）数学研究所于2000年5月24日在巴黎法兰西学院宣布了一件被媒体炒得火热的大事：对七个“千年数学难题”的每一个悬赏一百万美元。其中有一个已被解决(庞加莱猜想),还剩六个.（庞加莱猜想，已由俄罗斯数学家格里戈里·佩雷尔曼破解。我国中山大学朱熹平教授和旅美数学家、清华大学兼职教授曹怀东做了证明的封顶工作。）什么是NP完全问题NP完全问题排在百万美元大奖的首位，足见他的显赫地位和无穷魅力。在一个周六的晚上，你参加了一个盛大的晚会。由于感到局促不安，你想知道这一大厅中是否有你已经认识的人。你的主人向你提议说，你一定认识那位正在甜点盘附近角落的女士罗丝。不费一秒钟，你就能向那里扫视，并且发现你的主人是正确的。然而，如果没有这样的暗示，你就必须环顾整个大厅，一个个地审视每一个人，看是否有你认识的人。生成问题的一个解通常比验证一个给定的解时间花费要多得多。这是这种一般现象的一个例子。与此类似的是，如果某人告诉你，数１３，７１７，４２１可以写成两个较小的数的乘积，你可能不知道是否应该相信他，但是如果他告诉你它可以因式分解为３６０７乘上３８０３，那么你就可以用一个袖珍计算器容易验证这是对的。人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们于是就猜想，是否这类问题，存在一个确定性算法，可以在多项式时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。不管我们编写程序是否灵巧，判定一个答案是可以很快利用内部知识来验证，还是没有这样的提示而需要花费大量时间来求解，被看作逻辑和计算机科学中最突出的问题之一（斯蒂文·考克于１９７１年陈述）8.5一些典型的NP完全问题5部分NP完全问题树8.5.1合取范式的可满足性问题（CNF-SAT）6要证明CNF-SAT∈NPC，只要证明在Cook定理中定义的布尔表达式A，…，G或者已是合取范式，或者有的虽然不是合取范式，但可以用布尔代数中的变换方法将它们化成合取范式，而且合取范式的长度与原表达式的长度只差一个常数因子。问题描述：给定一个合取范式α，判定它是否可满足。如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称CNF(ConjunctiveNormalForm)。这里的因子是变量或。例如：就是一个合取范式，而就不是合取范式。xx))()((3213221xxxxxxx321xxx8.5.23元合取范式的可满足性问题（3-SAT）7证明思路：3-SAT∈NP是显而易见的。为了证明3-SAT∈NPC，只要证明CNF-SAT∝p3-SAT，即合取范式的可满足性问题可在多项式时间内变换为3-SAT。问题描述：给定一个3元合取范式α，判定它是否可满足。对于一个合取范式，若每个子句有且仅有3个变元时，它的可满足性问题便称为3SAT问题。定理3SAT问题属于NPC。下证8.5.3团问题CLIQUE9证明思路：已经知道CLIQUE∈NP。通过3-SAT∝pCLIQUE来证明CLIQUE是NP难的，从而证明团问题是NP完全的。问题描述：给定一个无向图G=(V，E)和一个正整数k，判定图G是否包含一个k团，即是否存在，V’V，|V’|=k，且对任意u，w∈V’有(u，w)∈E。8.5.4顶点覆盖问题（VERTEX-COVER）10证明思路：首先，VERTEX-COVER∈NP。因为对于给定的图G和正整数k以及一个“证书”V’，验证|V’|=k，然后对每条边(u，v)∈E，检查是否有u∈V’或v∈V’，显然可在多项式时间内完成。其次，通过CLIQUE∝pVERTEX-COVER来证明顶点覆盖问题是NP难的。问题描述：给定一个无向图G=(V，E)和一个正整数k，判定是否存在V’V，|V’|=k，使得对于任意(u，v)∈E有u∈V’或v∈V’。如果存在这样的V’，就称V’为图G的一个大小为k顶点覆盖。证将3SAT变换到VC.设U={u1,u2,...,un},C={c1,c2,...,cm}是3SAT的实例.如下构造图G,分量设计法.真值安排分量:Ti=(Vi,Ei),1in,其中Vi={ui,ūi},Ei={{ui,ūi}}任意覆盖必至少包含ui或ūi中的一个,否则不能覆盖边{ui或ūi}.满足性检验分量:Sj=(Vj’,Ej’),1jm,其中Vj’={a1[j],a2[j],a3[j]}Ej’={{a1[j],a2[j]},{a1[j],a3[j]},{a2[j],a3[j]}}覆盖至少包含Vj’中的两个顶点,否则不能覆盖Ej’中的三角形8.5.4顶点覆盖问题（VERTEX-COVER）联络边:沟通分量之间的关系对于每个子句cj,设cj={xj,yj,zj},则Ej’’={{a1[j],xj},{a2[j],yj},{a3[j],zj}}G=(V,E)V=(V1V2...Vn)(V1’V2’...Vm’)E=E1E2...En)(E1’E2’...Em’)(E1’’E2’’...Em’’)K=n+2m显然构造可在多项式时间完成8.5.4顶点覆盖问题（VERTEX-COVER）明纬电源，是微软公司的演示文稿软件。用户可以在投影仪或者计算机上进行演示，也可以将演示文稿打印出来，制作成胶片，以便应用到更广泛的领域中。利用MicrosoftOfficePowerPoint不仅可以创建演示文稿，还可以在互联网上召开面对面会议、远程会议或在网上给观众展示演示文稿。MicrosoftOfficePowerPoint做出来的东西叫演示文稿，其格式后缀名为：ppt、pptx；或者也可以保存为：pdf、图片格式等例如U={u1,u2,u3,u4},C={{u1,ū3,ū4},{ū1,u2,ū4}},则G如下，K=4+2×2=88.5.4顶点覆盖问题（VERTEX-COVER）设V’是V中不超过K的顶点覆盖,则V’中必包含Ti中的一个顶点和每个Ej’中的两个顶点,至少要n+2m个顶点.而K=n+2m,故V’中一定只包含每个Ti中的一个顶点和每个Ej’中的两个顶点.如下得到赋值uiV’t(ui)=TūiV’t(ui)=FEj’’中的三条边有两条被Vj’V’中的顶点覆盖,第三条必被V’Vi中的顶点覆盖.这表示在Vi中的这个顶点对应的文字取真.所以子句cj被满足.从而C被满足.设t:U{T,F}是满足C的一组赋值.若t(ui)=T,则在Ti中取顶点ui,否则取ūi.因为t满足子句cj,在Ej’’中的三条联络边中至少有一条被覆盖,那么取Ej’’中的另两条边的端点作为V’中的端点即可.8.5.4顶点覆盖问题（VERTEX-COVER）'')()(AAaAaasas实例：有穷集A，aA,s(a)Z+.问：是否存在A’A，使得证：显然均分是NP类问题。下面将3DM变换到均分问题设W,X,Y,MWXY是3DM的实例，其中|W|=|X|=|Y|=q，W={w1,w2,…,wq}X={x1,x2,…,xq}Y={y1,y2,…,yq}M={m1,m2,…,mk}8.5.5.均分NPC))(())(2())(3(222)(ihqpigqpifqpiasw1w2…wqx1x2…xqy1y2…yq02)23()13(130222...222ppqpqpqjpjBB的段数与s(ai)一样，每段的最右位为1，其它为0构造A，|A|=k+2对应于每个mi=(wf(i),xg(i),yh(i))有ai.s(ai)为二进制数，分成3q段，每段有p=log(k+1)位,共计3pq位，每段对应一个WXY中的元素.Wf(i),xg(i),yh(i)所代表的段的最右位为1，其它为0.注：plog(k+1)，2pk+1，k2p1,当k个1相加时不会产生段之间的进位令8.5.5.均分NPC例如：W={w1,w2},X={x1,x2},Y={y1,y2},M={(w1,x2,y2),(w1,x2,y1),(w2,x1,y1)}p=log(3+1)=2元素a1,a2,a3分别对应(w1,x2,y2),(w1,x2,y1),(w2,x1,y1)s(a1)=010000010001=210+24+20s(a2)=010000010100=210+24+22s(a3)=000101000100=28+26+22B=0101010101018.5.5.均分NPC子集A’={ai:1ik}满足BasAa')(当且仅当M’={mi:aiA’}是M的匹配A的最后两个元素b1,b2kiikiiBasbsBasbs1211)()()(2)(8.5.5.均分NPCkiiAAaAaasasas1'')(2)()(kiiasbsbs121)(3)()(假设A’A使得A’和A-A’的元素大小之和相等，即由于b1,b2不在同一子集，kiikiikiikiikiiAaasBasBasasbsbsasas1111211)(4)()(2)()()()()(8.5.5.均分NPC'11')()(2))(2()(AAakiikiiAaasasBBasas反之，若子集M’构成M的匹配，则A’={b1}{ai:miM’}满足因此A’-{b1}的元素对应的三元组构成M的匹配kiikiibAaBBasasas11}{'))(2()(2)(1考虑包含b1的子集A’,必有8.5.5.均分NPC限制法三元集合的恰当覆盖(X3C)最小覆盖问题集中集子图同构问题有界度的生成树0-1背包Knapsack多处理机调度8.5.6、NP完全性的证明方法局部替换法3SAT两点间的Hamilton通路问题区间排序分量设计法最小拖延排序8.5.6、NP完全性的证明方法限制法：通过对问题的实例加以限制得到一个已知NP完全问题的实例.例1三元集合的恰当覆盖(X3C)实例：有穷集S,|S|=3q,S的三元子集的集合C问：是否有C’C,使得S的每个元素恰好出现在C’的一个成员中.证明：限制S=WXY|W|=|X|=|Y|=qC={{w,x,y}|(w,x,y)WXY}则|C’|=q,且C’中任两个元素都不交，成为3DM问题8.5.6、NP完全性的证明方法例2最小覆盖问题实例：集合S的子集的集合C，正整数K.问：C是否有S的大小不超过K的覆盖，即是否包含子集C’C使得|C’|=K且C’=S？证明：限制cC,|c|=3,|S|=3K,则为X3C问题.例3集中集实例：集合S的子集的集合C，正整数K问：S是否包含C的大小不超过K的集中集（hittingset）,即是否有子集S’S,使得|S’|K,且S’至少包含C的每个子集的一个元素？证明：限制cC,|c|=2,令V=S,E=C,则构成图G=(V,E)的顶点覆盖问题.8.5.6、NP完全性的证明方法例4子图同构问题实例：图G=(V1,E1),H=(V2,E2)问：G中是否有同构于H的子图，即是否有子集VV1,EE1,使得|V|=|V2|,|E|=|E2|,且存在双射函数f：V2V,使得{u,v}E2{f(u),f(v)}E?证明