NP完全问题证明.ppt

几个NP完全问题,什么是NP完全问题,NP完全问题，是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。简单的写法是 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-SATNPC，只要证明在Cook定理中定义的布尔表达式A，G或者已是合取范式，或者有的虽然不是合取范式，但可以用布尔代数中的变换方法将它们化成合取范式，而且合取范式的长度与原表达式的长度只差一个常数因子。,问题描述：给定一个合取范式，判定它是否可满足。,如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称CNF(Conjunctive Normal Form)。这里的因子是变量 或 。例如： 就是一个合取范式，而 就不是合取范式。,8.5.2 3元合取范式的可满足性问题 （3-SAT）,7,证明思路： 3-SATNP是显而易见的。为了证明3-SATNPC，只要证明CNF-SATp 3-SAT，即合取范式的可满足性问题可在多项式时间内变换为3-SAT。,问题描述：给定一个3元合取范式，判定它是否可满足。,对于一个合取范式， 若每个子句有且仅有3个变元时， 它的可满足性问题便称为3SAT问题。 定理 3SAT问题属于NPC。下证,8.5.3 团问题CLIQUE,9,证明思路： 已经知道CLIQUENP。通过3-SATpCLIQUE来证明CLIQUE是NP难的，从而证明团问题是NP完全的。,问题描述：给定一个无向图G=(V，E)和一个正整数k，判定图G是否包含一个k团，即是否存在，VV，|V|=k，且对任意u，wV有(u，w)E。,8.5.4 顶点覆盖问题 （VERTEX-COVER）,10,证明思路： 首先，VERTEX-COVERNP。因为对于给定的图G和正整数k以及一个“证书”V，验证|V|=k，然后对每条边(u，v)E，检查是否有uV或vV，显然可在多项式时间内完成。 其次，通过CLIQUEpVERTEX-COVER来证明顶点覆盖问题是NP难的。,问题描述：给定一个无向图G=(V，E)和一个正整数k，判定是否存在VV，|V|=k，使得对于任意(u，v)E有uV或vV。如果存在这样的V，就称V为图G的一个大小为k顶点覆盖。,证 将3SAT变换到VC. 设U=u1,u2,.,un, C=c1,c2,.,cm是3SAT的实例. 如下构造图G, 分量设计法. 真值安排分量: Ti=(Vi,Ei), 1in, 其中Vi=ui,i, Ei=ui,i 任意覆盖必至少包含ui或i中的一个,否则不能覆盖边ui或i. 满足性检验分量: Sj=(Vj,Ej), 1 j m, 其中 Vj=a1j,a2j,a3j Ej=a1j,a2j,a1j,a3j,a2j,a3j 覆盖至少包含Vj中的两个顶点,否则不能覆盖Ej中的三角形,8.5.4 顶点覆盖问题 （VERTEX-COVER）,联络边: 沟通分量之间的关系 对于每个子句cj, 设cj = xj,yj,zj, 则 Ej=a1j,xj,a2j,yj,a3j,zj G = (V,E) V = (V1V2.Vn)(V1V2.Vm) E = E1E2.En)(E1E2.Em) (E1E2.Em) K = n +2m 显然构造可在多项式时间完成,8.5.4 顶点覆盖问题 （VERTEX-COVER）,重庆调查公司重庆私人侦探 奀莒哔,例如 U = u1,u2,u3,u4, C = u1,3,4,1,u2,4, 则G如下，K = 4 + 22 = 8,8.5.4 顶点覆盖问题 （VERTEX-COVER）,设V是V中不超过K的顶点覆盖, 则V中必包含Ti中的一个顶点和每个Ej中的两个顶点, 至少要n+2m个顶点. 而K=n+2m, 故V中一定只包含每个Ti中的一个顶点和每个Ej中的两个顶点. 如下得到赋值 uiV t(ui)=T iV t(ui)=F Ej中的三条边有两条被VjV中的顶点覆盖, 第三条必被VVi中的顶点覆盖. 这表示在Vi中的这个顶点对应的文字取真. 所以子句cj被满足. 从而C被满足. 设t: UT,F是满足C的一组赋值. 若t(ui)=T, 则在Ti中取顶点ui, 否则取i. 因为t满足子句cj, 在Ej中的三条联络边中至少有一条被覆盖, 那么取Ej中的另两条边的端点作为V中的端点即可.,8.5.4 顶点覆盖问题 （VERTEX-COVER）,实例：有穷集A，aA, s(a)Z+. 问：是否存在AA，使得,证：显然均分是NP类问题。下面将3DM变换到均分问题 设W,X,Y,M WXY 是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,B的段数与s(ai)一样，每段的最右位为1，其它为0,构造A，|A| = k +2 对应于每个mi = (wf(i),xg(i),yh(i) 有ai. s(ai)为二进制数，分成3q段，每段有p = log(k+1)位,共计3pq位，每段对应一个WXY中的元素. Wf(i),xg(i),yh(i) 所代表的段的最右位为1，其它为0.,注：plog(k+1)，2p k+1，k 2p1 , 当 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) = 01 00 00 01 00 01 = 210 + 24 + 20 s(a2) = 01 00 00 01 01 00 = 210 + 24 + 22 s(a3) = 00 01 01 00 01 00 = 28 + 26 + 22 B = 01 01 01 01 01 01,8.5.5. 均分NPC,子集A = ai:1ik 满足,当且仅当 M = mi: aiA是M的匹配 A的最后两个元素b1,b2,8.5.5. 均分NPC,假设A A使得A和A-A的元素大小之和相等，即,由于,b1,b2不在同一子集，,8.5.5. 均分NPC,反之，若子集M构成M的匹配，则 A = b1ai: miM 满足,因此A-b1的元素对应的三元组构成M的匹配,考虑包含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 = WXY |W|=|X|=|Y|=q C = w,x,y|(w,x,y)WXY 则|C|=q,且C中任两个元素都不交，成为3DM问题,8.5.6、NP完全性的证明方法,例2 最小覆盖问题 实例：集合S的子集的集合C，正整数K. 问： C是否有S的大小不超过K的覆盖，即是否包含子集C C 使得|C| =K 且C = S？ 证明：限制 cC,|c|=3,|S|=3K, 则为X3C问题. 例3 集中集 实例：集合S的子集的集合C，正整数K 问： S是否包含C的大小不超过K的集中集（hitting set）,即是否有子集SS,使得|S|K,且S至少包含C的每个子集的一个元素？ 证明： 限制cC,|c|=2, 令V=S, E=C, 则构成图G=(V,E)的顶点覆盖问题.,8.5.6、NP完全性的证明方法,例4 子图同构问题 实例：图G=(V1,E1), H=(V2,E2) 问：G中是否有同构于H的子图，即是否有子集VV1, EE1, 使得|V|=|V2|,|E|=|E2|,且存在双射函数f：V2V,使得 u,vE2 f(u),f(v)E? 证明：限制H为完全图，且|V2|=J, 则该问题是团的问题. 例5 有界度的生成树 实例：图G=(V,E), 正整数K=|V|1 问： G是否包含一棵顶点度数不超过K的生成树，即是否有子集EE, |E|=|V|1, 图G=(V,E)是连通的，且V中每个顶点至多包含在E的K条边中？ 证明：限制K=2，则为Hamilton通路问题,8.5.6、NP完全性的证明方法,例6 0-1背包Knapsack 实例：有穷集U，uU, 大小s(u)Z+, 价值 v(u)Z+, 大小的约束BZ+, 价值目标KZ+. 问：是否有子集UU，使得,证明：限制uU,则成为均分问题,8.5.6、NP完全性的证明方法,例7 多处理机调度 实例：有穷任务集A，aA, 长度l(a)Z+, 处理机台数 mZ+, 截止时间DZ+. 问：是否存在不交的集合A1,A2, ,Am, 使得,证明：限制,则成为均分问题.,8.5.6、NP完全性的证明方法,局部替换法：选择已知NP完全问题的实例中的某些元素作为基本单元，然后把每个基本单元替换成指定结构，从而得到目标问题的对应实例. 例8 3SAT 已知问题：SAT 目标问题：3SAT 基本单元：子句 子句集 例9 两点间的 Hamilton 通路 实例：G=(V,E)，u,vV. 问：G中是否存在一条从u到v的 Hamilton 通路？ 已知问题：HC 目标问题：两点间Hamilton通路 基本单元：顶点a u,v 证：对于HC的任一实例，任选顶点a, 用u,v代替a, 即 G=(V,E), V=(Va)u,v E=(Ea,v|a,vE)v,v,u,v|a,vE,8.5.6、NP完全性的证明方法,G G G有一条Hamilton回路当且仅当G有一条从u到v的Hamilton通路,替换实例,8.5.6、NP完全性的证明方法,例10 区间排序 实例：有穷任务集T,tT,开放时间r(t),截止时间d(t),需要时间l(t),其中r(t)N,d(t),l(t)Z+. 问：是否存在关于T的可行调度，即是否存在函数:T N 使得tT满足： (t)r(t) (t)+l(t)d(t) tTt, (t)+l(t)(t) 或 (t)+l(t)(t) ? 已知问题：均分 目标问题：区间排序 基本单元：A中元素 T中的任务,实施者,若B为偶数，则存在均分,证 设A和s(a)Z+ (aA) 为均分的实例. aA将a替换成taT,d(ta)=B+1，l(ta)=s(a) ，其中,B为奇数，则不能调度,8.5.6、NP完全性的证明方法,分量设计法 根据目标问题的实例设计分量(分量的成分与目标问题相关)，实现已知NPC问题的实例（分量的功能与已知问题相关）. 3SAT变换到VC，其中分量有真值安排分量、满足性检验分量等，这些分量都是子图，用来实现三元可满足性问题的实例. 例11 最小拖延排序 实例：任务集T，tT,完成时间l(t)=1,截止时间d(t)Z+. T上的偏序，非负整数K|T| 问：是否存在可行调度使得被拖延的任务数不超过K，即 : T0,1,|T|1, 使得 若tt, 则(t)(t) 若tt, 则(t)d(t)|K?,8.5.6、NP完全性的证明方法,证 将团变换到最小拖延排序. 设G=(V,E)是团问题的实例， 顶点分量：任务t，d(t)=|V|+|E| 边分量：任务t,d(t)=J(J+1)/2, 任务集：T=VE K=|E|J(J-1)/2 偏序：e=u,v，u,v任务完成后才能开始e任务, 即 tt tV,tE,t是t的一个端点,8.5.6、NP完全性的证明方法,设给定最小拖延排序的肯定实例，顶点任务不会拖延，只有边任务可能拖延，在截止时间之后完成的任务是被拖延的任务.拖延的任务数为|E|J(J-1)/2，不拖延的任务数为J(J-1)/2.而在之前安排的边数为 （在安排这些边之前至多安排J个顶点，而这些顶点构成大小为J的团）。 反之，若G中含大小为J的团，则先安排团的J个顶点任务，接着相关的J(J-1)/2个边任务，然后是剩下的顶点任务，那么被拖延的任务数为|E|J(J-1)/2.,8.5.6、NP完全性的证明方法,