第5讲证明NPC类问题的技术

1、第五讲上次内容：(1) P，NP ，NPC 类定义，第一个 NPC 问题， sat，NPC，(2) Cook 定理，第一个 NPC 问题，在 NTM 程序的帮助下完成了归约。(3) NPC 的含义，若一个 NPC 问题多项式时间可解，则所有 NP 问题多项式时间可解。 若一个 NPC 问题被证明不能多项式时间可解，则所有NP 问题均不能多项式时间可解。下面证明一些新的 NPC 问题。 NPC 问题不只一个。1 可以多项式时间求解2 可以多项式时间求解。1 可以多项式时间求解2 不可以多项式时间求解。1 不可以多项式时间求解2 不可以多项式时间求解。1 不可以多项式时间求解2 可以多项式时间求解

2、。 (不成立 )若 1 NPC， 2 NP， 1 2，则 2 NPC 。已知 sat NPC，从 SAT 开始证明其他 NPC，万事开头难。难在开始找不到合适的办法。已经证明了 SAT 是 NPC 了，其他问题是 NPC 的证明肯定与 SAT 不同了， 怎么做，做个样子看看。第四章：证明 NPC 类问题的技术SATKARP 的证明， 6 个 NPC 问题，一年时间。定理 4.1： 3sat NPC。(1) 证明在后面，先多讲几个问题 实例：布尔变量集合： U=u1,un，项集合： C = C1, C2, , Cm ，|Ci| = 3 询问：是否存在 U 的真值指派使 C 中所有项均满足？第1页

3、第五讲3 对集问题 3DM (2) 实际含义： 100 个编程人， 100 个数学推导， 100 个写文章的，组成 100 个 数学建模队，但并不是任意两人都可以分到同一队，所以每个人可以与他 人共事的选择并不是任意的。能组成吗？拉登组成恐怖小组。问题描述：实例：集合： W, X, Y，M W*X*Y。|W|=|X|=|Y| = q 询问：是否存在 M 的子集 MM，使|M|=q，M中没有任意两个 3 元组有 相同的分量。 完美匹配完美对集。例子：M=(w 1,x1,y1),(w2,x1,y3),(w3,x3,y3),(w1,x2,y1),(w2,x2,y3)M 中不存在 3 对集 M ，若

4、M 中再加上 (w3, x3, y2)则可以存在 M 了。 完美对集是： ( w1,x1,y1)，(w2,x2,y3)， (w3,x3,y2)顶点覆盖问题：背景，通信网络，结点设探测点，每条线路最少设一头 探测点，在网络上最少设几个探测点才能覆盖所有线路。例子图：实例： G=(V,E), 非负整数 K |V|， (3)询问：是否存在 V 的子集 V，|V| K，使任意 (u,v) E，有 u V或 v V， 总有。第2页第五讲团问题：背景， 从 100 人中选择 50 人，互相不认识。能选出来吗？ 例子：实例： G=(V, E)，一个非负整数 J |V| (4) 询问：是否存在 V的子集 VV

5、，使任意 u, v V，总有 (u,v) E 即 V 中的点形成 G 的一个完全子图。定理 4.1： 3SAT NPC 证明： SAT 的实例，描述 实例：布尔变量集合： U=u 1,un ，项集合： C=C 1,C2,Cm ， 询问：是否存在 U 的真值指派使 C 中所有项均满足？ 把上述实例变成一个 3SAT 的实例。 先面只用一个例子说明怎样变化的，任取一个 SAT 的实例： U= u1, u2, u3, u4, u5C=C 1,C2,C3,C4,C5C1=u 1C2=u 2,u4 C3=u 1,u3,u5C4= u1 ,u3 ,u4 ,u5C5=u 1,u2,u3,u4 ,u5第3页第

6、五讲把这个实例变成 3SAT 的实例，怎么做？(1) 针对 C1增加两个变量 y11, y12，把 C1变成 4个项。 (u1,y11,y12)，(u1, y11,y12)，(u1,y11, y12)，(u1 , y11 , y12 ) 存在性对应：若 C1满足，则上述 4 项均满足。(2) 针对 C2增加 1个变量 y21 ，把 C2变成 2个项 (u2,u4 ,y21)，(u2 ,u4 , y21 )C2满足则，上述 2 项都满足。(3) 一切不变(u1,u3 ,u5)，已经是 3SAT 了。(4) 针对 C4增加一个变量 y41 ，将 C4变成两个项 C4= u1, u3, u4, u5

7、 (u1, u3, y41)，(y41,u4, u5) 说明满足的对应性(5)针对 C5增加 2 变量 y 51,y52 ，将 C5变成 3 项 C5=u 1,u2,u3,u4 ,u5(u1, u2, y51)， ( y51, u3, y52)，(y52, u4, u5)说明满足的对称性。 假设 u1, u2, u3, u4 , u5都取假，就会观察到 y51, y52的取值总会导致三个项有 个不满足，因此三个项有一个满足，一定 C5 满足。Sat 满足 3SAT 满足3SAT 满足 SAT 满足， 往往在反向存在性证明不好说。 所以证明了结论。定理 4.2 3DM NPC 证明： 3DM N

8、P 很显然， 验证给定解是否完美匹配 。3SAT 3DM ，下面通过举例子说明规约，不然没法说明白，要用对集的语 言说明 Sat 问题可满足性。第4页第五讲U= u1,u2,u3,u4,u5C=C1=(u1,u2,u3),C2=(u2,u3,u4),C3=(u3,u4,u5),C4=(u1,u2,u4),C5=(u2,u3 ,u5),C6=(u1, u4,u5)|U|= n =5，|C| = m = 6全取 1 就能满足，没问题，当然能满足。 要构造的东西： W, X, Y ， M W*X*YW = u11, u11 , u12, u12, u16, u16, u21, u21, , u26,

9、 u26 , u51, u51, , u56, u56 ，|W|=2mn = 60。多少个变量： 60 个变量。X=A S1 G1A=a 11,a 12, ,a15,a16, , a51, a52, a56 ，30个元素。 |A|=mn=30 S1=s11,s16， 实际上描述那个变量在那个项中出现。 |S1|=m=6G1=g 11,g 12, ,g124 ，|G1|=m(n-1)=24Y=B S2 G2B= b11,b 12, ,b15,b 16, ,b56S2=s21,s26G2=g 21, ,g224下面开始造 3 元组，分为 3 大类(1)T 类：测试真值指派类第5页T1t=(u11,

10、a11,b11),(u12,a12,b12),( u13, a13,b 13 ),( u14,a14,b14),(u15,a15,b15),(u16,a16,b16)T1f= ( u11, a 12,b 11 ),( u12, a 13,b 12),( u13, a 14,b 13 ),( u14, a 15,b 14 ),( u15, a 16,b 15 ),( u16, a11,b16)T1=T1t T1f中最多能够选择 6个三元组， 当恰好选择 6个 3元组时， 只能选 择T1t或T1f ，这就表达了 u1取 0(T)还是取 1(F)。同理可以构造 T2, T3, T4, T5u11u2

11、6a2122b266u126b22u25u12a23u13u15a25b24a24u23u14u1423u21T2t =( u21,a21,b21),( u22,a22,b22),(u23, a23,b 23 ), ( u2 4 ,a24,b 24 ), ( u2 5 ,a25,b 25 ), (u26, a26,b 26)T2f =( u21, a22,b21 ),( u22, a23,b22),(u23, a24,b23),(u24, a25,b24),( u25, a26,b 25),( u26, a21,b 26 ) 对应 u21-6, u2 1-6, a21-6, b21-6第6页第

12、五讲T3t =( u31,a31,b31),(u32,a32,b32),(u33, a33,b33), (u34,a34,b34), ( u35 ,a35,b 35 ), (u36, a36,b 36)T3f =( u31, a32,b31 ),( u32, a33,b32),(u33, a34,b 33 ),( u34, a35,b34),( u35, a36,b 35),( u36, a31,b36) u31-6, u3 1-6, a31-6, b31-6T4t =( u41,a41,b41),( u42,a42,b42),(u43, a43,b 43 ), ( u4 4 ,a44,b 4

13、4 ), ( u4 5 ,a45,b 45 ), (u46, a46,b 46)T4f =( u41, a42,b41 ),( u42, a43,b42),(u43, a44,b 43 ),( u44, a45,b44),( u45, a46,b 45),( u46, a41,b 46 ) u41-6, u4 1-6, a41-6, b41-6T5t =( u51,a51,b51),(u52,a52,b52),(u53, a53,b53), ( u5 4 ,a54,b 54 ), (u55,a55,b55), (u56, a56,b 56)T5f =( u51, a52,b51 ),( u52

14、, a53,b52),(u53, a54,b 53 ),( u54, a55,b54),( u55, a56,b 55),( u56, a51,b56) u51-6, u5 1-6, a51-6, b51-6|T1 T2 T3 T4 T5|=2mn已经是 60 个 3 元组了。 ui 要么占用了 ui1-6, 要么占用了 ui 1-6 ，最多选出 30个三元组，若选出 30个的话，一定是要么 Tit全选，要么 Tif全选。A 和 B 全部用完了 (30个元素)。W 中的 ui1-6或ui 1-6只用了 30个元素。 (2)类，测试可满足类：测试项的可满足性。C1 = (u1, u2, u3),

15、 表达一个布尔变量出现在第 1 个项中。C1(3dm)= (u11, s11, s 21) , (u21, s11, s 21), (u 31, s11, s21) 只关心一个变量的赋值使项满足，只能选择一个三元组， 3 选 1，能选出 来就不错了。与前面的 T 类很有关系。C2=(u2,u3,u4), 表达一个布尔变量出现在第 2 个项中。C2(3dm)=( u22,s12,s22),(u32,s12,s22),(u 42,s12,s22)第7页第五讲C3=(u3,u4,u5), 表达一个布尔变量出现在第3 个项中。C3(3dm)= (u33,s13,s23),(u43,s13,s23),(

16、u 53,s13,s23) 一个元素只能选一次。C4=(u1,u2,u4), 表达一个布尔变量出现在第4 个项中。C4(3dm)= (u14,s14,s24),(u24,s14,s24),(u 44,s 14,s 24) C5=(u2,u3 ,u5), 表达一个布尔变量出现在第 5 个项中。, s15, s25) ,( u35, s15, s25),C6=( u1,u4,u5)，表达一个布尔变量出现在第6C6(3dm)=( u16,s16,s26),(u46,s16,s26), 在测试真值指派中， ui*的或 u i * 出现过了。在测试可满足类中，出现 ui ，则全为 ui ，不然则全为 u

17、i 。 最多选出 m(6)个三元组。 选出一个三元组来就有一个项满足了。 什么情况导致选不出 m 个三元组呢？解释一下。 例如在 C6中选择第一项，其它三元组中就不能选择带u11-6 的三元组了从 T 类选 30 个 3 元组确定真值指派，从 C 类选 6 个 3 元组确定是否 6 个项都满足， W 还剩 24 个布尔变量。每 个布尔变量最多出现 6 次。(1) 可以考虑 u1=u2=u3=u4=u5=T 和 u1=u2=u3=T, u4=u5=F 的情况加以说明。(2) 说明选择两个红圈是不可能的 如果能够选出 6 个三元组，则最后一定使 6 个项都满足。就看哪个赋值使该项满足了。可以讲满足

18、情况与完美匹配的关系了(3)类，填补类：2mnm(n-1)=2m2n(n-1) 。G=( u11, g11, g21), ,(u11, g124, g224), ,(u56, g11, g21), ,(u56, g124, g224),( u11,g11,g21), ,(u11,g124,g224), (u56,g11,g21), ,( u5 6, g124, g224)从填补类一定能选出 24 个三元组，但不能超过 24 个， m(n-1) 个 若存在真值指派使 3SAT 的项均满足，第8页第五讲( ) 若 3sat 有真值指派使每个项满足，对应可以取出30 个真值指派类 3元组， 6 个满

19、足项 3 元组， 24 个填补 3 元组，正好 60 个。( ) 若 3dm 可以选出 60 个 3 元组，会发现必选出 30 个真值指派类 3 元组， 6 个满足项 3 元组， 24 个填补类 3 元组，于是得到满足每个项的布尔变量 真指派。图的独立集问题：实例：图 G=(V,E)，正整数 K ，询问：是否存在 V 的子集 V，满足任意两点 u,v V ，(u,v) E，|V | K。 顶点覆盖：实例：图 G=(V,E)，正整数 L 。询问： 是否存在 V 的子集 V，满足 |V| L，任意边 (u,v) E， u,v V 。 定理： VC NPC.证明： 3SAT VC设： 3SAT 实例为： U= u1,u2,u3,u4 ，C= u1,u2,u3, u1,u3,u4 , u2,u3,u4 构造 VC 实例如下： L=n+2m证明，