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

上次内容： (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问题，一年时间。 定理4.1：3sat(NPC。(1) 证明在后面，先多讲几个问题 实例：布尔变量集合：U={u1,…,un}， 项集合：C = {C1, C2, …, Cm}，|Ci| = 3 询问：是否存在U的真值指派使C中所有项均满足？ 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’，总有。 团问题：背景，从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,} C3={u1,,u5} C4={,u3,,u5} C5={u1,,,,u5} 把这个实例变成3SAT的实例，怎么做？ (1)针对C1增加两个变量{y11, y12}，把C1变成4个项。 (u1,y11,y12)，(u1,,y12)，(u1,y11,)，(u1,,) 存在性对应：若C1满足，则上述4项均满足。 (2)针对C2增加1个变量{y21}，把C2变成2个项 (u2,,y21)，(u2,,) C2满足则，上述2项都满足。 (3)一切不变 (u1,,u5)，已经是3SAT了。 (4)针对C4增加一个变量{y41}，将C4变成两个项C4={, u3, , u5} (, u3, y41)，(,, u5) 说明满足的对应性 (5)针对C5增加2变量{y51,y52}，将C5变成3项C5={u1,,,,u5} (u1, , y51)，(, , y52)，(, , u5) 说明满足的对称性。假设u1, , , , u5都取假，就会观察到y51, y52的取值总会导致三个项有一个不满足，因此三个项有一个满足，一定C5满足。 Sat满足(3SAT满足 3SAT满足(SAT满足，往往在反向存在性证明不好说。 所以证明了结论。 定理4.2 3DM(NPC 证明：3DM(NP很显然，验证给定解是否完美匹配。 3SAT(3DM，下面通过举例子说明规约，不然没法说明白，要用对集的语言说明Sat问题