§5.6 基本NP完全问题的证明.

Presentation on theme: "§5.6 基本NP完全问题的证明."— Presentation transcript:

1 §5.6 基本NP完全问题的证明

2 定理1 三可满足问题(3SAT)是NP完全问题。
(证) 整个证明过程分成两步， 先证 3SAT∈NP， 再证明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的实例为 ①集合U＝{u1,u2,…,um} ②公式F＝{c1,c2,…,cn}， 其中ci (i＝1，2，…，n)是项。 以U及F为输入，g为3SAT构造实例U′及F′如下所述:

5 U′ = U ∪ U′1 ∪ U′2 ∪ … ∪ U′n F′ = C′1 ∪ C′2 ∪ … ∪ C′n 其中C′j 是项的集合，且每一项含三个因子 因此F′也是项的集合，所以F′是公式。 由上两式可见: 逻辑变量集合U增加一些变量， 再改写公式F的每一项为项集合， 就得到三可满足问题的实例。 还需证明F′是可满足的充分必要条件为 F是可满足的。

6 为定义映射g，只须说明如何构造C′j 及U′j .
公式F的项Cj是因子的集合 Cj ＝{Z1，Z2，…，ZK } 即| Cj |＝K， Cj由K个因子组成。 C′j 及U′j的构成按K的值 分四种情况讨论。

7 K＝l， Cj ＝ {z1}，则U′j及C′j构造为
U′j ＝ {yj1, yj2 } 增加两个逻辑变量而已 C′j＝{{z1,yj1, ⌉yj2},{z1, ⌉yj1,yj2 },{z1, yj1,yj2 }, {z1, ⌉yj1, ⌉yj2 }} 即C′j含四个项。 将Cj一个项替换为四个项. 注意: 这四个项穷尽两个逻辑变量yj1, yj2 的四种情况

8 K＝2， Cj ＝{z1 ，z2}，则 U′j ＝ {yj} 仅仅增加一个逻辑变量 C′j ＝ { {z1，z2，yj}，{z1，z2，⌉yj}} 即C′j含两项。 将Cj一个项替换为两个项. 注意: 这两个项穷尽一个逻辑变量yj 的两种情况

9 K＝3， Cj ＝{z1 ，z2 ，z3}，则 U′j ＝ Φ C′j ＝ { {z1 ，z2 ， z3}} 即C′j含一项。
不增加逻辑变量 C′j ＝ { {z1 ，z2 ， z3}} 即C′j含一项。

10 U′j ＝ {yj1,yj2 ,…,yjk-3 }, 增加K - 3个逻辑变量 C′j ＝{ {z1,z2 ,yj1} ,
K>3， Cj ＝{z1,z2 ,…,zk }，则 U′j ＝ {yj1,yj2 ,…,yjk-3 }, 增加K - 3个逻辑变量 C′j ＝{ {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}} 即C′j含(K一2)项, 比| U′j |大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′为真； 从而只要给诸U′j的各逻辑变量赋值 保持U的逻辑变量的赋值不变, 并使F′为真即可

13 因集合 　　(U′－U) 中的逻辑变量被划分为集合U′j ， U′j中的逻辑变量仅出现在相应的C′j中, 因此只须证明， 映射f′可以逐次扩展到各集合U′j， 每次扩展使C′j中的项的值都为真．

14 同样分四种情况， ①K＝1， 用数理逻辑的方法很容易证明C′j和Cj恒等，(P7) 即C′j的值只与z1有关， 因f已经满足Cj ， 则f′不论给yj1, yj2赋什么值都能使C′j满足。

15 ②K=2，同样可用数理逻辑 证明C′j和Cj恒等， 即C′j的值只与z1 ，z2有关， 因f已经满足Cj， 则不论f给yj赋什么值, 都可使C′j满足

16 ③K=3，(P9) U′j为空， 且C′j只含一个项, 就是Cj, 已被f满足。 Cj已经含三个因子, 被f赋值， 因此f, 不用给任何新逻辑变量赋值。

17 ④K>3， Cj= {z1,z2 ,…,zk }，因f已满足Cj， 此即Cj的K个因子中至少一个为真， 设zi为真， 按i的值分三种情况, 讨论如何扩展映射f

18 (ⅰ) i为1或2，则令 yj1=yj2 =…= yjK-3=假 这使C′j的每一项都为真。 (ⅱ)如i为K－4或K －3，则令 yj1=yj2 =…= yjK-3= 真 这也使C′j的每一项都为真。 (ⅲ)如2<i<K－4，则令 yj1=yj2 =…= yji-2= 真 yji-1=yji =…= yjK-3= 假 这又使C′j的每一项都为真。

19 这就证明了公式F′中所有的C′j都被满足，
也就证明了公式F′被我们构造的映射f′满足。 现在证明如F′可满足，则F亦可满足。 设存在映射 f′： U′→{真, 假} 使公式F′值为真. 如何定义映射 f ?

20 定义映射 f：U →{真，假} 为 f(u)＝ f′(u) (u∈U) U是U′的子集，如u∈U，则u∈U′ 现在证明f满足公式F，即f使公式F的值为真。

21 此即, C′j 被满足, 要证明Cj也能被满足 ① K＝l，C′j有四项 (P7) 这四个项穷尽两个逻辑变量yj1, yj2的四种情况 不论给yj1, yj2赋什么值, 一定有某个项的后两个因子值均假, 这就是说z1必定为真. 所以, Cj被满足了.

22 这两个项穷尽逻辑变量yj1的两种情况 不论给yj1赋什么值, 必有一项的最后一个因子为假, 这就是说z1和z2必定有一个为真.
② K＝2，C′j有两项 这两个项穷尽逻辑变量yj1的两种情况 不论给yj1赋什么值, 必有一项的最后一个因子为假, 这就是说z1和z2必定有一个为真. 所以, Cj被满足了.

23 ③ K＝3， C′j只含有一项, 与Cj相同 既然C′j满足了, 当然Cj也满足了.

24 皆假, 用“假”替代C′j中的诸z，再简化C′j
④ K>3， f′满足C′j，则只须证明f′使 z1，z2，···，zk 中至少有一个的值为真。用反证法. 令 z1,z2 ,…,zk 皆假, 用“假”替代C′j中的诸z，再简化C′j 则C′j等价为

25 C′j ＝{ {yj1} , {⌉yji-3,yji-2}, {⌉yji-2,yji-1}, {⌉yji-1,yji},…,
{⌉yjk-4,yjk-3}, {⌉yjk-3}} 因C′j被满足，则其各项之值皆“真”。 第一项之值为真，则必有 f′(yj1)＝真

26 第二项{⌉yj1,yj2}等价于{yj2}，其值为真，则必有
f′(yj2)＝真 以此类推，由Cj的倒数第二项为“真”知，必有 f′(yjK-3) ＝真 但是由此确定的映射没能满足C′j 因为C′j的最后一项 {⌉yjk-3} 必定为假，从而使C′j值为假，即公式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)为含三个因子的项

29 由3SAT的实例, 映射g构造VC问题的实例有以下四步骤。
①对每一个逻辑变量ui∈ U，构造子图 该子图由两个节点ui ，⌉ui 及一条边组成。 ui ⌉ui

30 ②对每一项Ci∈ F构造子图 vi2 vi vi3 以Ci的三个因子为顶点, 建造一个三角形(有三条边)

31 则连接节点u(由①构造)和节点vij(由②构造) 如vij＝ ⌉u， 则连接节点⌉u和节点vij 由以上三步得到VC实例的图。
③对项Ci＝{vi1,vi2 ,vi3}中每个因子 vij(j＝1, 2, 3), 如vij＝u (u ∈ U)， 则连接节点u(由①构造)和节点vij(由②构造) 如vij＝ ⌉u， 则连接节点⌉u和节点vij 由以上三步得到VC实例的图。 ④令K=n+2m, n=|U| m=|F|

32 证明之前, 给一个例子.

33 F＝ {{ul，⌉u3， ⌉u4}，{⌉ul，u2， ⌉u4}， {u2，u3，u4}}
设3SAT问题有如下实例 U = {u1，u2，u3，u4} F＝ {{ul，⌉u3， ⌉u4}，{⌉ul，u2， ⌉u4}， {u2，u3，u4}} ul ⌉ul u2 ⌉u2 u ⌉u3 u4 ⌉u4 K=10 显然实例是可满足的，f如上所示。 真 真 假 假

34 为证明本定理,须证明两件事. ⒈ VC ∈ NP 设VC问题的实例G = (V, E) 构造一不确定算法，该算法第一阶段猜一个V′⊂V(V′是V的子集,且|V′|=K) 第二阶段检测V′是否为G的K覆盖. 这阶段的时间复杂度是多项式的. 所以VC问题可由多项式时间不确定算法解决 因此,VC ∈ NP

35 下面证明3SAT的实例可满足的充分必要条件是: 它在VC的像实例有K覆盖.
⒉ 前面定义的映射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 又因为②的构造方法, 每个项 Ci＝{vi1,vi2 ,vi3} 的三个因子至少一个(记作v)的值为真. v对应着②构造的子图中的一个结点, 除去它,将另两个结点选入覆盖, 它们覆盖了三角形的三条边 共选入了2m个结点 (该项对应着②构造的子图——三角形)

39 v是三角形中的一个结点, 它和①的线段的一端相连接. 总共选入了n+2m个结点. 将证明这构成了VC实例的K覆盖.

40 由①构造的n条线段和②构造的三角形的3m条边已经被它们覆盖
每个三角形有两个结点被选入, 相应的两条边被覆盖 第三个结点(v)没有被选入,但是与之相连的、在①的线段里的端点被选入. 所以, 第三条边也被覆盖了.

41 充分性得证, 下面证明必要性 先设其在VC的像实例有K覆盖, 欲证明3SAT问题的实例可满足

42 每条线段的两端点必有一端在K覆盖,否则该线段无法覆盖 共n个结点 由此定义映射f(u)如下: f(u)=真 否则f(u)=假
注意到K=n+2m 考虑由①建造的线段, 每条线段的两端点必有一端在K覆盖,否则该线段无法覆盖 共n个结点 由此定义映射f(u)如下: 若与u对应的线段的左侧结点在覆盖则 f(u)=真 否则f(u)=假

43 考虑由②建造的三角形, 为覆盖这三边, 必有两个顶点在K覆盖, 共2m个结点. 注意: 已经有了n+2m=K个结点. 考虑由③添加的三条线段, 三角形有两个顶点在K覆盖, 与之相连的两线段则被覆盖, 第三个顶点v没有入选K覆盖,

44 该结点对应的逻辑变量赋值为真 第三顶点v的赋值为真; 该结点对应的逻辑变量赋值为假 第三顶点v的赋值也为真 若这个端点是线段的左侧结点则
所以由③添加的第三条线段的覆盖责任,必定由不在三角形的端点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. (V—V′ )是G的独立集合 3. (V—V′ )是G的补图G′ ＝(V，E′)的集团, 其中 E′＝ {(u, v) | u、v∈ V，(u，v) ∉ E} 引理通过独立集合将覆盖与集团联系起来

48 证 引理可以分三步来证明 ① ② ③ l ⇒ ⇒ ⇒ 1 ①l ⇒ 2, 使用反证法 设(V—V′ )不是G的独立集合 则存在两点u、v ∈ (V—V′ ), 但是 (u, v ) ∈ E 因为u、v ∈ (V—V′ ),所以 u、v ∉ V′ 这与“V′是G的覆盖”矛盾(V′没有覆盖边(u, v ))

49 ②2 ⇒ 3 (V—V′ )是G的独立集合 任意两点u、v ∈ (V—V′ ), 则(u, v ) ∉ E 根据补图的定义, 有(u, v ) ∈ E′, 所以, (V—V′ )是G的补图G′ ＝(V，E′)的集团

50 ③ 3 ⇒ 1 (V—V′ )是G的补图G′ ＝(V，E′)的集团, 用反证法证明V′是G的覆盖。 设V′不是G的覆盖，则 G中存在边(u，v) ∈ E，但是 u ∉ V′，v ∉ V′， 则必有 u ∈ V—V′, v ∈ V—V′， 因(V—V′)是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完全问题
由定理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完全问题