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

上次内容：

(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可以多项式时间求解。(不成立)

若1NPC，2NP，12，则2NPC。

已知satNPC，从SAT开始证明其他NPC，万事开头难。

 难在开始找不到合适的办法。

已经证明了SAT是NPC了，其他问题是NPC的证明肯定与SAT不同了，怎么做，做个样子看看。 第四章：证明NPC类问题的技术

KARP的证明，6个NPC问题，一年时间。

3DM PAR SAT 3SAT CL VC HC 定理4.1：3satNPC。(1) 证明在后面，先多讲几个问题 实例：布尔变量集合：U={u1,…,un}，

项集合：C = {C1, C2, …, Cm}，|Ci| = 3

询问：是否存在U的真值指派使C中所有项均满足？

第1页

第五讲

 3对集问题3DM (2)

实际含义：100个编程人，100个数学推导，100个写文章的，组成100个数学建模队，但并不是任意两人都可以分到同一队，所以每个人可以与他人共事的选择并不是任意的。能组成吗？拉登组成恐怖小组。 问题描述：

实例：集合：W, X, Y，M  W*X*Y。|W|=|X|=|Y| = q

询问：是否存在M的子集M’M，使|M’|=q，M’中没有任意两个3元组有相同的分量。完美匹配完美对集。 例子：

M={(w1,x1,y1),(w2,x1,y3),(w3,x3,y3),(w1,x2,y1),(w2,x2,y3)}

M中不存在3对集M’，若M中再加上(w3, x3, y2)则可以存在M’了。 完美对集是：{(w1,x1,y1)，(w2,x2,y3)，(w3,x3,y2)}

 顶点覆盖问题：背景，通信网络，结点设探测点，每条线路最少设一头探测点，在网络上最少设几个探测点才能覆盖所有线路。例子图：

是否存在2个点覆盖所有边? 实例：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的子集V’V，使任意u, vV’，总有(u,v)E。

即V’中的点形成G的一个完全子图。

定理4.1：3SATNPC 证明：SAT的实例，描述

实例：布尔变量集合：U={u1,…,un}，

项集合：C={C1,C2,…,Cm}，

询问：是否存在U的真值指派使C中所有项均满足？ 把上述实例变成一个3SAT的实例。

先面只用一个例子说明怎样变化的，任取一个SAT的实例： U={u1, u2, u3, u4, u5} C={C1,C2,C3,C4,C5} C1={u1} C2={u2,u}

4C3={u1,u,u5}

3C4={u,u3,u,u5}

14C5={u1,u,u,u,u5}

234第3页

第五讲

把这个实例变成3SAT的实例，怎么做？

(1)针对C1增加两个变量{y11, y12}，把C1变成4个项。 (u1,y11,y12)，(u1,y,y12)，(u1,y11,y)，(u1,y,y)

11

1211

12存在性对应：若C1满足，则上述4项均满足。 (2)针对C2增加1个变量{y21}，把C2变成2个项 (u2,u,y21)，(u2,u,y)

4421C2满足则，上述2项都满足。 (3)一切不变

(u1,u,u5)，已经是3SAT了。

3(4)针对C4增加一个变量{y41}，将C4变成两个项C4={u, u3, 1u4, u5} (u, u3, y41)，(y,u, u5)

1414说明满足的对应性

(5)针对C5增加2变量{y51,y52}，将C5变成3项C5={u1,u,u,u,u5} 234(u1, u2, y51)，(y51, u3, y52)，(y52, u4, u5)

2说明满足的对称性。假设u1, uSat满足3SAT满足

, u3, u4, u5都取假，就会观察到y51, y52的取值总会导致三个项有一

个不满足，因此三个项有一个满足，一定C5满足。

3SAT满足SAT满足，往往在反向存在性证明不好说。 所以证明了结论。 定理4.2 3DMNPC

证明：3DMNP很显然，验证给定解是否完美匹配。

3SAT3DM，下面通过举例子说明规约，不然没法说明白，要用对集的语言说明Sat问题可满足性。

第4页

第五讲

U={u1,u2,u3,u4,u5}

C={C1=(u1,u2,u3),C2=(u2,u3,u4),C3=(u3,u4,u5),C4=(u1,u,u4),C5=(u2,u,u5),C6=(u,

231u4,u)}

5|U|= n =5，|C| = m = 6

全取1就能满足，没问题，当然能满足。 要构造的东西：W, X, Y，MW*X*Y W = {u1[1],

u1[1], u1[2], u1[2],…, u1[6], u1[6], u2[1],u2[1], …, u2[6],u2[6],…, u5[1],

u5[1], …, u5[6],u5[6]}，|W|=2mn = 60。

多少个变量：60个变量。 X=AS1G1

A={a1[1],a1[2],…,a1[5],a1[6],…, a5[1], a5[2]…, a5[6]}，30个元素。|A|=mn=30 S1={s1[1],…,s1[6]}，实际上描述那个变量在那个项中出现。|S1|=m=6 G1={g1[1],g1[2],…,g1[24]}，|G1|=m(n-1)=24 Y=BS2G2

B={b1[1],b1[2],…,b1[5],b1[6],…,b5[6]} S2={s2[1],…s2[6]} G2={g2[1],…,g2[24]}

下面开始造3元组，分为3大类 (1)T类：测试真值指派类

第5页

第五讲

u1[6] u1[1]a1[1] b1[1] u1[1] a1[2] u[2]1b1[2] u1[2] a1[3] b1[3] u1[3]b1[4] a1[4] u1[3] u1[6]b1[6] a1[6] u1[5] b1[5] u1[5]a1[5] u1[4] u1[4] T1t={(u1[1],a1[1],b1[1]),(u1[2],a1[2],b1[2]),(u1[3], a1[3],b1[3]),(u1[4],a1[4],b1[4]),(u1[5],a1[5],b1[5]),(u1[6],

a1[6],b1[6])}

T1f={( u1[1], a1[2],b1[1]),( u1[2], a1[3],b1[2]),( u1[3], a1[4],b1[3]),( u1[4], a1[5],b1[4]),( u1[5], a1[6],b1[5]),( u1[6],

a1[1],b1[6])}

T1=T1tT1f中最多能够选择6个三元组，当恰好选择6个3元组时，只能选择T1t或T1f，这就表达了u1取0(T)还是取1(F)。 同理可以构造T2, T3, T4, T5

u2[6] u1[1]a2[1] b2[1] u2[1] a2[2] u[2]1b2[2] u1[2] a2[3] b2[3] u1[3]b2[4] a2[4] u2[3] u1[6]b2[6] a2[6] u2[5] b2[5] u1[5]a2[5] u1[4] u1[4] T2t={(u2[1],a2[1],b2[1]),(u2[2],a2[2],b2[2]),(u2[3], a2[3],b2[3]), (u2[4],a2[4],b2[4]), (u2[5],a2[5],b2[5]),

(u2[6], a2[6],b2[6])}

T2f={(u2[1], a2[2],b2[1]),( u2[2], a2[3],b2[2]),( u2[3], a2[4],b2[3]),( u2[4], a2[5],b2[4]),( u2[5], a2[6],b2[5]),( u2[6],

u2[1-6],u2[1-6], a2[1-6], b2[1-6] 第6页

a2[1],b2[6])}对应

第五讲

T3t={(u3[1],a3[1],b3[1]),(u3[2],a3[2],b3[2]),(u3[3], a3[3],b3[3]), (u3[4],a3[4],b3[4]), (u3[5],a3[5],b3[5]),

(u3[6], a3[6],b3[6])}

T3f={(u3[1], a3[2],b3[1]),( u3[2], a3[3],b3[2]),( u3[3], a3[4],b3[3]),( u3[4], a3[5],b3[4]),( u3[5], a3[6],b3[5]),( u3[6],

a3[1],b3[6])} u3[1-6],u3[1-6], a3[1-6], b3[1-6] T4t={(u4[1],a4[1],b4[1]),(u4[2],a4[2],b4[2]),(u4[3], a4[3],b4[3]), (u4[4],a4[4],b4[4]), (u4[5],a4[5],b4[5]),

(u4[6], a4[6],b4[6])}

T4f={(u4[1], a4[2],b4[1]),( u4[2], a4[3],b4[2]),( u4[3], a4[4],b4[3]),( u4[4], a4[5],b4[4]),( u4[5], a4[6],b4[5]),( u4[6],

[1-6], a4[1-6], b4[1-6] a4[1],b4[6])} u4[1-6],u4T5t={(u5[1],a5[1],b5[1]),(u5[2],a5[2],b5[2]),(u5[3], a5[3],b5[3]), (u5[4],a5[4],b5[4]), (u5[5],a5[5],b5[5]),

(u5[6], a5[6],b5[6])}

T5f={(u5[1], a5[2],b5[1]),( u5[2], a5[3],b5[2]),( u5[3], a5[4],b5[3]),( u5[4], a5[5],b5[4]),( u5[5], a5[6],b5[5]),( u5[6],

a5[1],b5[6])} u5[1-6],u5[1-6], a5[1-6], b5[1-6]

|T1T2T3T4T5|=2mn

已经是60个3元组了。ui要么占用了ui[1-6],要么占用了u[1-6]，最多选出i30个三元组，若选出30个的话，一定是要么T全选，要么T全选。A和B

tifi全部用完了(30个元素)。W中的ui[1-6]或ui[1-6]只用了30个元素。 (2)类，测试可满足类：测试项的可满足性。

C1 = (u1, u2, u3), 表达一个布尔变量出现在第1个项中。

C1(3dm)={(u1[1], s1[1], s2[1]), (u2[1], s1[1], s2[1]), (u3[1], s1[1], s2[1])} 只关心一个变量的赋值使项满足，只能选择一个三元组，3选1，能选出来就不错了。与前面的T类很有关系。

C2=(u2,u3,u4), 表达一个布尔变量出现在第2个项中。 C2(3dm)={(u2[2],s1[2],s2[2]),(u3[2],s1[2],s2[2]),(u4[2],s1[2],s2[2])}

第7页

第五讲

C3=(u3,u4,u5), 表达一个布尔变量出现在第3个项中。 C3(3dm)={(u3[3],s1[3],s2[3]),(u4[3],s1[3],s2[3]),(u5[3],s1[3],s2[3])}

一个元素只能选一次。

C4=(u1,u,u4), 表达一个布尔变量出现在第4个项中。 2C4(3dm)={ (u1[4],s1[4],s2[4]),(u[4],s1[4],s2[4]),(u4[4],s1[4],s2[4])}

2C5=(u2,u,u5), 表达一个布尔变量出现在第5个项中。 3C5(3dm)={ (u2[5],s1[5],s2[5]),(u[5],s1[5],s2[5]),(u5[5],s1[5],s2[5])} 3C6=(u,u4,u)，表达一个布尔变量出现在第6个项中。 15C6(3dm)={(u[6],s1[6],s2[6]),(u4[6],s1[6],s2[6]),(u[6],s1[6],s2[6])} 15在测试真值指派中，ui[*]的或ui[*]出现过了。在测试可满足类中，出现ui[•]，则全为ui[•]，不然则全为ui[•]。最多选出m(6)个三元组。选出一个三元组来就有一个项满足了。什么情况导致选不出m个三元组呢？解释一下。例如在C6中选择第一项，其它三元组中就不能选择带u1[1-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个项都满足。就看哪个赋值使该项满足了。可以讲满足情况与完美匹配的关系了。 (3)类，填补类：2mn[m(n-1)]=2m2n(n-1)。 G={(u1[1],g1[1],g2[1]),…,(u1[1],g1[24],g2[24]),…, …………

(u5[6],g1[1],g2[1]),…,(u5[6],g1[24],g2[24]), {(u[1],g1[1],g2[1]),…,(u[1],g1[24],g2[24]),

11…, (u[6],g1[1],g2[1]),…,(u[6],g1[24],g2[24])}

55从填补类一定能选出24个三元组，但不能超过24个，m(n-1)个。 若存在真值指派使3SAT的项均满足，

第8页

第五讲

()若3sat有真值指派使每个项满足，对应可以取出30个真值指派类3元组，6个满足项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

u1 u1u2 u2u3 u3u4 u4A1 A2 A3 B1 C1 B2 C2 B3 C3 证明，蓝边，黑边，红边。覆盖蓝边最少需要n个点，覆盖黑边，最少需要2m个点。红边怎么覆盖？

真值指派u1,u2,u3,u4全部赋真，则u1,u2,u3,u4覆盖全部蓝边喝每个三角形上

第9页

第五讲

至少一条红边。其余边只用六个点可全部覆盖。

若存在顶点覆盖，一定是每个三角形两个点，每条蓝边一个点，这样不会冲突，所以有真值指派。 集问题：

实例：图G=(V,E)，正整数M。

询问：是否存在V的子集V’，满足|V’|M，任意u, vV’，(u,v)E。 定理：IVS(Idpendent Vertex Set)NPC。最大集问题是NPC类。 证明：可将顶点覆盖问题归约到集问题。一个图V1是顶点覆盖，则V\\V1是集。

u1 u1u2 u2u3 u3u4 u4A1 A2 A3 B1 C1 B2 C2 B3 C3 , M = |V|-L=17-10=7。

团问题：CL 实例：G=(V, E)，一个非负整数J|V| 询问：是否存在V的子集V’V，使任意u, vV’，总有(u,v)E。 定理：CLNPC。团问题是NPC类。 证明：最大集问题归约到团问题。 补图：

第10页

第五讲

1 1 1 6 2 6 2 6 2 5 3 5 3 5 3 4 4 4 J=n-L

原图中有L顶点的顶点覆盖补图中有n-L顶点的团。定理4.4：HCNPC HC的描述： 实例：图G=(V,E)

询问：G中是否含有一个hamilton圈？

解释什么是hamilton圈：走遍所有点，点不重复的圈。 例子：下面的实例，是顶点覆盖的实例，

a b d c k=2,是否存在两个点的顶点集合，覆盖所有边。

第11页

,