基本NP完全问题的证明.ppt

1,5.6 基本NP完全问题的证明,2,定理1 三可满足问题(3SAT)是NP完全问题。 (证) 整个证明过程分成两步， 先证 3SATNP， 再证明SAT 3SAT 3SAT NP是显然的，因为很容易构造一不确定算法， 该算法第一阶段猜一个函数 f： U真, 假。,3,然后，第二阶段检测公式F的值， 这只需将公式F中的所有因子u及u分别用f(u)和f(u)的补替代， 即用“真”或“假”替代， 再对逻辑式求值。 容易看出，第二阶段所需时间是m和n的多项式 其中m是集合U的逻辑变量的个数， n是公式F的项的个数。,4,SAT 3SAT就不那末明显了。 先构造映射 g：SAT 3SAT 其中SAT表示可满足性问题的实例之集合 3SAT表示三可满足性问题的实例的集合。 然后再证明g是多项式转换。 SAT的实例为 集合Uu1,u2,um 公式Fc1,c2,cn， 其中ci (i1，2，n)是项。 以U及F为输入，g为3SAT构造实例U及F如下所述:,5,U = U U1 U2 Un F = C1 C2 Cn 其中Cj 是项的集合，且每一项含三个因子 因此F也是项的集合，所以F是公式。 由上两式可见: 逻辑变量集合U增加一些变量， 再改写公式F的每一项为项集合， 就得到三可满足问题的实例。 还需证明F是可满足的充分必要条件为 F是可满足的。,6,为定义映射g，只须说明如何构造Cj 及Uj . 公式F的项Cj是因子的集合 Cj Z1，Z2，ZK 即| Cj |K， Cj由K个因子组成。 Cj 及Uj的构成按K的值 分四种情况讨论。,7,Kl， Cj z1，则Uj及Cj构造为 Uj yj1, yj2 增加两个逻辑变量而已 Cjz1,yj1, yj2,z1, yj1,yj2 ,z1, yj1,yj2 , z1, yj1, yj2 即Cj含四个项。 将Cj一个项替换为四个项. 注意: 这四个项穷尽两个逻辑变量yj1, yj2 的四种情况,8,K2， Cj z1 ，z2，则 Uj yj 仅仅增加一个逻辑变量 Cj z1，z2，yj，z1，z2，yj 即Cj含两项。 将Cj一个项替换为两个项. 注意: 这两个项穷尽一个逻辑变量yj 的两种情况,9,K3， Cj z1 ，z2 ，z3，则 Uj 不增加逻辑变量 Cj z1 ，z2 ， z3 即Cj含一项。,10,K3， Cj z1,z2 ,zk ，则 Uj yj1,yj2 ,yjk-3 , 增加K - 3个逻辑变量 Cj z1,z2 ,yj1 , z3, yj1,yj2, z4, yj2,yj3, , z i-1, yji-3,yji-2, z i , yji-2,yji-1, zi+1, yji-1,yji, zk-2, yjk-4,yjk-3, zk-1,zk ,yjk-3 即Cj含(K一2)项, 比| Uj |大1。 若K=4, 则含两项.,若K=4, 则增一个变量 第一项和最后一项各含两个z(原变量)和一个y(新增变量). 其余各项含一个z和两个y(其中一个是因子的非),11,显然，映射g为3SAT问题计算一个实例所需时间为m和n的多项式。 要增加n个变量集合, 对应F中的n个项. 每个集合至多含m-3个变量, m为U中因子的个数 要把n个项改写为n个 项集合 每个集合至多含m-2个项, 每项有三个因子.,12,现在证明如F可满足, 则F也可满足. 设 f： U真, 假 能使F值为真。 因U是U的子集, 只须证明f可以扩展为 f： U真, 假 并使公式F为真； 从而只要给诸Uj的各逻辑变量赋值 保持U的逻辑变量的赋值不变, 并使F为真即可,13,因集合 (UU) 中的逻辑变量被划分为集合Uj ， Uj中的逻辑变量仅出现在相应的Cj中, 因此只须证明， 映射f可以逐次扩展到各集合Uj， 每次扩展使Cj中的项的值都为真,14,同样分四种情况， K1， 用数理逻辑的方法很容易证明Cj和Cj恒等，(P7) 即Cj的值只与z1有关， 因f已经满足Cj ， 则f不论给yj1, yj2赋什么值都能使Cj满足。,15,K=2，同样可用数理逻辑 证明Cj和Cj恒等， 即Cj的值只与z1 ，z2有关， 因f已经满足Cj， 则不论f给yj赋什么值, 都可使Cj满足,16,K=3，(P9) Uj为空， 且Cj只含一个项, 就是Cj, 已被f满足。 Cj已经含三个因子, 被f赋值， 因此f, 不用给任何新逻辑变量赋值。,17,K3， Cj= z1,z2 ,zk ，因f已满足Cj， 此即Cj的K个因子中至少一个为真， 设zi为真， 按i的值分三种情况, 讨论如何扩展映射f,18,() i为1或2，则令 yj1=yj2 = yjK-3=假 这使Cj的每一项都为真。 ()如i为K4或K 3，则令 yj1=yj2 = yjK-3= 真 这也使Cj的每一项都为真。 ()如2iK4，则令 yj1=yj2 = yji-2= 真 yji-1=yji = yjK-3= 假 这又使Cj的每一项都为真。,19,这就证明了公式F中所有的Cj都被满足， 也就证明了公式F被我们构造的映射f满足。 现在证明如F可满足，则F亦可满足。 设存在映射 f： U真, 假 使公式F值为真. 如何定义映射 f ?,20,定义映射 f：U 真，假 为 f(u) f(u) (uU) U是U的子集，如uU，则uU 现在证明f满足公式F，即f使公式F的值为真。,21,此即, Cj 被满足, 要证明Cj也能被满足 Kl，Cj有四项 (P7) 这四个项穷尽两个逻辑变量yj1, yj2的四种情况 不论给yj1, yj2赋什么值, 一定有某个项的后两个因子值均假, 这就是说z1必定为真. 所以, Cj被满足了.,22, K2，Cj有两项 这两个项穷尽逻辑变量yj1的两种情况 不论给yj1赋什么值, 必有一项的最后一个因子为假, 这就是说z1和z2必定有一个为真. 所以, Cj被满足了.,23, K3， Cj只含有一项, 与Cj相同 既然Cj满足了, 当然Cj也满足了.,24, K3， f满足Cj，则只须证明f使 z1，z2，zk 中至少有一个的值为真。用反证法. 令 z1,z2 ,zk 皆假, 用“假”替代Cj中的诸z，再简化Cj 则Cj等价为,25,Cj yj1 , yj1,yj2, yj2,yj3, , yji-3,yji-2, yji-2,yji-1, yji-1,yji, yjk-4,yjk-3, yjk-3 因Cj被满足，则其各项之值皆“真”。 第一项之值为真，则必有 f(yj1)真,26,第二项yj1,yj2等价于yj2，其值为真，则必有 f(yj2)真 以此类推，由Cj的倒数第二项为“真”知，必有 f(yjK-3) 真 但是由此确定的映射没能满足Cj 因为Cj的最后一项 yjk-3 必定为假，从而使Cj值为假，即公式F值为假，这与f满足F的假设矛盾。,27,这反证了Cj中诸因子 z1,z2 ,zk 至少有一个为真，这使Cj值为真. 因此映射f使公式F满足。证毕。,28,定理2 顶点覆盖问题(VC)是NP完全问题。 证明过程梗概 先定义3SAT VC的多项式转换f. 3SAT问题的实例为两个集合 U u1,u2,un F C1,C2,Cm 其中Ci(i=1，2，m)为含三个因子的项,由3SAT的实例, 映射g构造VC问题的实例有以下四步骤。 对每一个逻辑变量ui U，构造子图 该子图由两个节点ui ，ui 及一条边组成。,ui,ui,30,对每一项Ci F构造子图 vi2 vi1 vi3 以Ci的三个因子为顶点, 建造一个三角形(有三条边),31,对项Civi1,vi2 ,vi3中每个因子 vij(j1, 2, 3), 如viju (u U)， 则连接节点u(由构造)和节点vij(由构造) 如vij u， 则连接节点u和节点vij 由以上三步得到VC实例的图。 令K=n+2m, n=|U| m=|F|,32,证明之前, 给一个例子.,33,设3SAT问题有如下实例 U = u1，u2，u3，u4 F ul，u3， u4，ul，u2， u4， u2，u3，u4 ul ul u2 u2 u3 u3 u4 u4 K=10 显然实例是可满足的，f如上所示。,真 真 假 假,34,为证明本定理,须证明两件事. VC NP 设VC问题的实例G = (V, E) 构造一不确定算法，该算法第一阶段猜一个VV(V是V的子集,且|V|=K) 第二阶段检测V是否为G的K覆盖. 这阶段的时间复杂度是多项式的. 所以VC问题可由多项式时间不确定算法解决 因此,VC NP,35, 前面定义的映射g是从3SAT到VC的多项式转换。 g的四步骤的时间复杂度都是多项式的 所以g的复杂度也是多项式的 下面证明3SAT的实例可满足的充分必要条件是: 它在VC的像实例有K覆盖.,36,先设3SAT问题的实例可满足,欲证明其在VC的像实例有K覆盖 存在映射f, 给逻辑变量集合U的各个u赋值, 使得F的所有项 C1,C2,Cm 的值均为真. 构造VC的像实例的K覆盖如下.,37,考虑每一个逻辑变量u, 若映射f给u的赋值为真, 则将构造的线段的左侧端点选入覆盖 否则, 把右侧端点选入覆盖 入选的有n个结点 它们覆盖了构造的n条线段,38,又因为的构造方法, 每个项 Civi1,vi2 ,vi3 的三个因子至少一个(记作v)的值为真. v对应着构造的子图中的一个结点, 除去它,将另两个结点选入覆盖, 它们覆盖了三角形的三条边 共选入了2m个结点 (该项对应着构造的子图三角形),39,v是三角形中的一个结点, 它和的线段的一端相连接. 总共选入了n+2m个结点. 将证明这构成了VC实例的K覆盖.,40,由构造的n条线段和构造的三角形的3m条边已经被它们覆盖 下面证明连接的3m条边也被覆盖 每个三角形有两个结点被选入, 相应的两条边被覆盖 第三个结点(v)没有被选入,但是与之相连的、在的线段里的端点被选入. 所以, 第三条边也被覆盖了.,41,充分性得证, 下面证明必要性 先设其在VC的像实例有K覆盖, 欲证明3SAT问题的实例可满足,42,注意到K=n+2m 考虑由建造的线段, 每条线段的两端点必有一端在K覆盖,否则该线段无法覆盖 共n个结点 由此定义映射f(u)如下: 若与u对应的线段的左侧结点在覆盖则 f(u)=真 否则f(u)=假,43,考虑由建造的三角形, 为覆盖这三边, 必有两个顶点在K覆盖, 共2m个结点. 注意: 已经有了n+2m=K个结点. 考虑由添加的三条线段, 三角形有两个顶点在K覆盖, 与之相连的两线段则被覆盖, 第三个顶点v没有入选K覆盖,44,所以由添加的第三条线段的覆盖责任,必定由不在三角形的端点u承担 这个端点u必定就是前一页的入选端点, 若这个端点是线段的左侧结点则 该结点对应的逻辑变量赋值为真 第三顶点v的赋值为真; 若这个端点是线段的右侧结点则 该结点对应的逻辑变量赋值为假 第三顶点v的赋值也为真,45,所以, 三角形对应的项的逻辑值因而为真 所以公式F的值也就是真 所以3SAT的实例可满足. 证毕,46,定义 图G(V, E)的独立集合V是V的子集 且如u、v V，则(u，v) E， 即V中的任两个节点之间不存在边。 如|V|K，则V，称为G的K独立集合。 独立集合问题(简称IS) 实例：图G(V，E)及正整数J|V| 问：G是否有独立集合V且|V| J,47,引理 图G(V，E)， V是V的子集V V. 下述三命题是等价的： 1. V是G的覆盖 2. (VV )是G的独立集合 3. (VV )是G的补图G (V，E)的集团, 其中 E (u, v) | u、v V，(u，v) E 引理通过独立集合将覆盖与集团联系起来,48,证 引理可以分三步来证明 l 2 3 1 l 2, 使用反证法 设(VV )不是G的独立集合 则存在两点u、v (VV ), 但是 (u, v ) E 因为u、v (VV ),所以 u、v V 这与“V是G的覆盖”矛盾(V没有覆盖边(u, v ),49,2 3 (VV )是G的独立集合 任意两点u、v (VV ), 则(u, v ) E 根据补图的定义, 有(u, v ) E, 所以, (VV )是G的补图G (V，E)的集团,50, 3 1 (VV )是G的补图G (V，E)的集团, 用反证法证明V是G的覆盖。 设V不是G的覆盖，则 G中存在边(u，v) E，但是 u V，v V， 则必有 u VV, v VV， 因(VV)是G的集团，则 (u，v) E 由补图定义知 (u，v) E 这与前面假设矛盾。定理证毕.,51,引理告诉我们, 覆盖、独立集合、集团三者只是同一个问题的不同叙述。 上述引理提供了极为简单的方法， 可将一个问题转换为其它两个问题。譬如， 欲将顶点覆盖问题转换为集团问题，只需映射 f：VC CL 由VC的实例：G(V, E)及正整数K，映射f构造CL的实例：图G(G的补图)和 正整数J|V|K,52,因此只要证这三个问题中一个是NP完全问题 就证明了三个问题都是NP完全问题. 由定理2可证得定理3。 定理3 集团问题(CL)和独立集合问题(IS)是NP完全问题,53,定理4 哈密尔顿回路问题(HC)是NP完全问题 下一节5-8给出定理的完整证明 先用定理4的结论证明巡回售货员问题(TS) 是NP完全问题。,54,定理5 巡回售货员问题(TS)是NP完全问题 定理5的证明很简单，本章第四节的例子已经证明 HC TS 又TS NP是明显的， 定理4结论为 哈密尔顿问题(HC)是NP完全问题， 所以TS问题是NP完全问题,