基本NP完全问题的证明.ppt-淘文阁

资源描述

《基本NP完全问题的证明.ppt》由会员分享，可在线阅读，更多相关《基本NP完全问题的证明.ppt（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、5.6 基本基本NP完全问题的证明完全问题的证明1定理定理1 三可满足问题三可满足问题(3SAT)是是NP完全完全问题。问题。(证证)整个证明过程分成两步，整个证明过程分成两步，先证先证 3SATNP，再证明再证明SAT 3SAT3SAT NP是显然的，因为很容易构是显然的，因为很容易构造一不确定算法，造一不确定算法，该算法第一阶段猜一个函数该算法第一阶段猜一个函数 f：U真真,假假。2然后，第二阶段检测公式然后，第二阶段检测公式F的值，的值，这只需将公式这只需将公式F中的所有因子中的所有因子u及及 u分分别用别用f(u)和和f(u)的补替代，的补替代，即用即用“真真”或或“假假”替代，替代，

2、再对逻辑式求值。再对逻辑式求值。容易看出，第二阶段所需时间是容易看出，第二阶段所需时间是m和和n的多项式的多项式其中其中m是集合是集合U的逻辑变量的个数，的逻辑变量的个数，n是公式是公式F的项的个数。的项的个数。3SAT 3SAT就不那末明显了。就不那末明显了。先构造映射先构造映射 g：SAT 3SAT其中其中SAT表示可满足性问题的实例之集合表示可满足性问题的实例之集合3SAT表示三可满足性问题的实例的集合。表示三可满足性问题的实例的集合。然后再证明然后再证明g是多项式转换是多项式转换。SAT的实例为的实例为集合集合Uu1 1,u2,um m公式公式Fc1 1,c2,cn n，其中其中ci(

3、i1，2，n)是项。是项。以以U及及F为输入，为输入，g为为3SAT构造实例构造实例U及及F如下所述如下所述:4U=U U1 U2 Un F=C1 C2 Cn其中其中Cj 是项的集合，且每一项含三个因子是项的集合，且每一项含三个因子因此因此F也是项的集合，所以也是项的集合，所以F是公式。是公式。由上两式可见由上两式可见:逻辑变量集合逻辑变量集合U增加一些变量，增加一些变量，再改写公式再改写公式F的每一项为项集合，的每一项为项集合，就得到三可满足问题的实例。就得到三可满足问题的实例。还需证明还需证明F是可满足的充分必要条件为是可满足的充分必要条件为F是可满足的。是可满足的。5为定义映射为定义映射

4、g，只须说明如何构造只须说明如何构造Cj 及及Uj.公式公式F的项的项Cj是因子的集合是因子的集合 Cj Z1，Z2，ZK 即即|Cj|K，Cj由由K个因子组成。个因子组成。Cj 及及Uj的构成按的构成按K的值的值分四种情况讨论。分四种情况讨论。6Kl，Cj z1，则则Uj及及Cj构造为构造为 Uj yj1,yj2 增加两个逻辑变量而已增加两个逻辑变量而已Cjz1,yj1,yj2,z1,yj1,yj2,z1,yj1,yj2,z1,yj1,yj2 即即Cj含四个项。含四个项。将将Cj一个项替换为四个项一个项替换为四个项.注意注意:这四个项这四个项穷尽穷尽两个逻辑变量两个逻辑变量yj1,yj2 的

5、的四种情况四种情况7K2，Cj z1，z2，则，则 Uj yj仅仅增加一个逻辑变量仅仅增加一个逻辑变量 Cj z1，z2，yj，z1，z2，yj 即即Cj含两项。含两项。将将Cj一个项替换为两个项一个项替换为两个项.注意注意:这两个项这两个项穷尽穷尽一个逻辑变量一个逻辑变量yj 的的两种情况两种情况8K3，Cj z1，z2，z3，则则 Uj 不增加逻辑变量不增加逻辑变量 Cj z1，z2，z3 即即Cj含含一项。一项。9K3，Cj z1,z2,zk，则则 Uj yj1,yj2,yjk-3,增加增加K-3个逻辑变量个逻辑变量 Cj z1,z2,yj1,z3,yj1,yj2,z4,yj2,yj3,

6、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(其中一个是因子的其中一个是因子的非非)10显然，映射显然，映射g为为3SAT问题计算一个实例问题计算一个实例所需时间为所需时间为m和和n的多项式。的多项式。要增加要增加n个变量

7、集合个变量集合,对应对应F中的中的n个项个项.每个集合至多含每个集合至多含m-3个变量个变量,m为为U中因中因子的个数子的个数要把要把n个项改写为个项改写为n个个项集合项集合每个集合至多含每个集合至多含m-2个项个项,每项有三个每项有三个因子因子.11现在证明如现在证明如F可满足可满足,则则F也可满足也可满足.设设 f：U真真,假假能使能使F值为真。值为真。因因U是是U的子集的子集,只须证明只须证明f可以扩展为可以扩展为 f：U真真,假假并使公式并使公式F为真；为真；从而只要给诸从而只要给诸Uj的各逻辑变量赋值的各逻辑变量赋值保持保持U的逻辑变量的赋值不变的逻辑变量的赋值不变,并使并使F为真

8、即可为真即可12因集合因集合(UU)中的逻辑变量被划分为集合中的逻辑变量被划分为集合Uj，Uj中的逻辑变量仅出现在相应的中的逻辑变量仅出现在相应的Cj中中,因此只须证明，因此只须证明，映射映射f可以逐次扩展到各集合可以逐次扩展到各集合Uj，每次扩展使每次扩展使Cj中的项的值都为真中的项的值都为真13同样分四种情况，同样分四种情况，K1，用数理逻辑的方法很容易证明用数理逻辑的方法很容易证明Cj和和Cj恒等，恒等，(P7)即即Cj的值只与的值只与z1有关，有关，因因f已经满足已经满足Cj，则则f不论给不论给yj1,yj2赋什么值都能使赋什么值都能使Cj满足。满足。14K=2，同样可用数理逻辑，同样

9、可用数理逻辑证明证明Cj和和Cj恒等，恒等，即即Cj的值只与的值只与z1，z2有关，有关，因因f已经满足已经满足Cj，则不论则不论f给给yj赋什么值赋什么值,都可使都可使Cj满足满足15K=3，(P9)Uj为空，为空，且且Cj只含一个项只含一个项,就是就是Cj,已被已被f满足。满足。Cj已经含三个因子已经含三个因子,被被f赋值，赋值，因此因此f,不用给任何新逻辑变量赋值。不用给任何新逻辑变量赋值。16K3，Cj=z1,z2,zk，因，因f已满足已满足Cj，此即此即Cj的的K个因子中至少一个为真，个因子中至少一个为真，设设zi为真，为真，按按i的值分三种情况的值分三种情况,讨论如何扩展映射讨论如

10、何扩展映射f17()()i为为1或或2，则令，则令 yj1=yj2=yjK-3=假假这使这使Cj的每一项都为真。的每一项都为真。()()如如i为为K4或或K 3，则令，则令 yj1=yj2=yjK-3=真真这也使这也使Cj的每一项都为真。的每一项都为真。()()如如2i3，f满足满足Cj，则只须证明，则只须证明f使使 z1，z2，zk中至少有一个的值为真。用反证法中至少有一个的值为真。用反证法.令令 z1,z2,zk皆假皆假,用用“假假”替代替代Cj中的诸中的诸z，再简化，再简化Cj 则则Cj等价为等价为24Cj yj1,yj1,yj2,yj2,yj3,yji-3,yji-2,yji-2,

11、yji-1,yji-1,yji,yjk-4,yjk-3,yjk-3 因因Cj被满足，则其各项之值皆被满足，则其各项之值皆“真真”。第一项之值为真，则必有第一项之值为真，则必有 f(yj1)真真25第二项第二项 yj1,yj2等价于等价于yj2，其值为真，则必有，其值为真，则必有 f(yj2)真真以此类推，由以此类推，由Cj的倒数第二项为的倒数第二项为“真真”知，必有知，必有 f(yjK-3)真真但是由此确定的映射没能满足但是由此确定的映射没能满足Cj因为因为Cj的最后一项的最后一项 yjk-3必定为假，从而使必定为假，从而使Cj值为假，即公式值为假，即公式F值为假，值为假，这与这与f满足满足

12、F的假设矛盾。的假设矛盾。26这反证了这反证了Cj中诸因子中诸因子 z1,z2,zk至少有一个为真，这使至少有一个为真，这使Cj值为真值为真.因因此映射此映射f使公式使公式F满足。证毕。满足。证毕。27定理定理2 顶点覆盖问题顶点覆盖问题(VC)是是NP完全完全问题。问题。证明过程梗概证明过程梗概先定义先定义3SAT VC的多项式转换的多项式转换f.3SAT问题的实例为两个集合问题的实例为两个集合 U u1 1,u2,un n F C1 1,C2,Cm m其中其中Ci i(i=1，2，m)为含三个因子的项为含三个因子的项28由由3SAT的实例的实例,映射映射g构造构造VC问题的实例问题的实例有

13、以下四步骤。有以下四步骤。对每一个逻辑变量对每一个逻辑变量ui i U，构造子图，构造子图该子图由两个节点该子图由两个节点ui i，ui i 及一条边组成。及一条边组成。uiui29对每一项对每一项Ci i F构造子图构造子图 vi2i2 vi1 i1 vi3i3以以Ci i的三个因子为顶点的三个因子为顶点,建造一个三角形建造一个三角形(有三条边有三条边)30对项对项Ci ivi1,vi2,vi3中每个因子中每个因子 vij(j1,2,3),如如viju(u U)，则连接节点则连接节点u(由由构造构造)和节点和节点vij(由由构造构造)如如vij u，则连接节点则连接节点 u和节点和节点vij

14、由以上三步得到由以上三步得到VC实例的图。实例的图。令令K=n+2m,n=|U|m=|F|K=n+2m,n=|U|m=|F|31证明之前证明之前,给一个例子给一个例子.32设设3SAT3SAT问题有如下实例问题有如下实例 U=u1U=u1，u2u2，u3u3，u4u4 F F ulul，u3u3，u4u4，ulul，u2u2，u4u4，u2u2，u3u3，u4u4 ulul ulul u2 u2 u2 u3 u2 u3 u3 u4 u3 u4 u4u4 K=10 K=10显然实例是可满足的，显然实例是可满足的，f f如上所示。如上所示。真真真真假假假假33 为证明本定理为证明本定理,须证

15、明两件事须证明两件事.VC VC NP NP 设设VCVC问题的实例问题的实例G=(V,E)G=(V,E)构造一不确定算法，该算法第一阶段猜一构造一不确定算法，该算法第一阶段猜一个个V VV(V(V V是是V V的子集的子集,且且|V V|=K)|=K)第二阶段检测第二阶段检测V V是否为是否为G G的的K K覆盖覆盖.这阶段的时间复杂度是多项式的这阶段的时间复杂度是多项式的.所以所以VCVC问题可由多项式时间不确定算法解决问题可由多项式时间不确定算法解决因此因此,VC,VC NP NP34 前面定义的映射前面定义的映射g是从是从3SAT到到VC的多项式的多项式转换。转换。g的的四步骤的时间复

16、杂度都是多项式的四步骤的时间复杂度都是多项式的所以所以g的复杂度也是多项式的的复杂度也是多项式的下面证明下面证明3SAT的实例可满足的充分必要的实例可满足的充分必要条件是条件是:它在它在VC的像实例有的像实例有K覆盖覆盖.35先设先设3SAT问题的实例可满足问题的实例可满足,欲证明其欲证明其在在VC的像实例有的像实例有K覆盖覆盖存在映射存在映射f,给逻辑变量集合给逻辑变量集合U的各个的各个u赋值赋值,使得使得F的所有项的所有项 C1 1,C2,Cm m的值均为真的值均为真.构造构造VC的像实例的的像实例的K覆盖如下覆盖如下.36考虑每一个逻辑变量考虑每一个逻辑变量u,若映射若映射f给给u的赋值

17、为真的赋值为真,则将则将构构造的线段的左侧端点选入覆盖造的线段的左侧端点选入覆盖否则否则,把右侧端点选入覆盖把右侧端点选入覆盖入选的有入选的有n个结点个结点它们覆盖了它们覆盖了构造的构造的n条线段条线段37又因为又因为的构造方法的构造方法,每个项每个项 C Ci ivvi1i1,v,vi2i2,v,vi3i3 的三个因子至少一个的三个因子至少一个(记作记作v)v)的值为真的值为真.v v对应着对应着构造的子图中的一个结点构造的子图中的一个结点,除去它除去它,将另两个结点选入覆盖将另两个结点选入覆盖,它们覆盖了三角形的三条边它们覆盖了三角形的三条边共选入了共选入了2m2m个结点个结点(该项对应着

18、该项对应着构造的子图构造的子图三角形三角形)38v v是三角形中的一个结点是三角形中的一个结点,它和它和的线段的一端相连接的线段的一端相连接.总共选入了总共选入了n+2mn+2m个结点个结点.将证明这构成了将证明这构成了VCVC实例的实例的K K覆盖覆盖.39由由构造的构造的n n条线段和条线段和构造的三角形构造的三角形的的3m3m条边已经被它们覆盖条边已经被它们覆盖下面证明下面证明连接的连接的3m3m条边也被覆盖条边也被覆盖每个三角形有两个结点被选入每个三角形有两个结点被选入,相应的相应的两条边被覆盖两条边被覆盖第三个结点第三个结点(v)(v)没有被选入没有被选入,但是与之相但是与之相连的、

19、在连的、在的线段里的端点被选入的线段里的端点被选入.所以所以,第三条边也被覆盖了第三条边也被覆盖了.40充分性得证充分性得证,下面证明必要性下面证明必要性先设其在先设其在VCVC的像实例有的像实例有K K覆盖覆盖,欲证明欲证明3SAT3SAT问题的实例可满足问题的实例可满足41注意到注意到K=n+2mK=n+2m考虑由考虑由建造的线段建造的线段,每条线段的两端点必有一端在每条线段的两端点必有一端在K K覆盖覆盖,否则该线段无法覆盖否则该线段无法覆盖共共n n个结点个结点由此定义映射由此定义映射f(uf(u)如下如下:若与若与u u对应的线段的左侧结点在覆盖则对应的线段的左侧结点在覆盖则 f(u

20、f(u)=)=真真否则否则f(uf(u)=)=假假42考虑由考虑由建造的三角形建造的三角形,为覆盖这三边为覆盖这三边,必有两个顶点在必有两个顶点在K K覆覆盖盖,共共2m2m个结点个结点.注意注意:已经有了已经有了n+2m=Kn+2m=K个结点个结点.考虑由考虑由添加的三条线段添加的三条线段,三角形有两个顶点在三角形有两个顶点在K K覆盖覆盖,与之相与之相连的两线段则被覆盖连的两线段则被覆盖,第三个顶点第三个顶点v v没有入选没有入选K K覆盖覆盖,43所以由所以由添加的第三条线段的覆盖责任添加的第三条线段的覆盖责任,必必定由不在三角形的端点定由不在三角形的端点u u承担承担这个端点这个端点u

21、 u必定就是前一页的入选端点必定就是前一页的入选端点,若若这个端点是这个端点是线段的左侧结点则线段的左侧结点则该结点对应的逻辑变量赋值为真该结点对应的逻辑变量赋值为真第三顶点第三顶点v v的赋值为真的赋值为真;若若这个端点是这个端点是线段的右侧结点则线段的右侧结点则该结点对应的逻辑变量赋值为假该结点对应的逻辑变量赋值为假第三顶点第三顶点v v的赋值也为真的赋值也为真44所以所以,三角形对应的项的逻辑值因三角形对应的项的逻辑值因而为真而为真所以公式所以公式F的值也就是真的值也就是真所以所以3SAT的实例可满足的实例可满足.证毕证毕45定义定义图图G(V,E)的的独立集合独立集合V是是V的子集的

23、盖与集团联系起来引理通过独立集合将覆盖与集团联系起来47证证引理可以分三步来证明引理可以分三步来证明 l 2 3 1 l 2,使用反证法使用反证法设设(VV)不是不是G的独立集合的独立集合则存在两点则存在两点u、v (VV),但是但是 (u,v)E E因为因为u、v (VV),所以所以 u、v V 这与这与“V是是G的覆盖的覆盖”矛盾矛盾(V没有覆盖边没有覆盖边(u,v)482 3(VV)是是G的独立集合的独立集合任意两点任意两点u、v (VV),则则(u,v)E E根据补图的定义根据补图的定义,有有(u,v)E E,所以所以,(VV)是是G的补图的补图G(V，E)的集团的集团49 3 1

24、(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这与前面假设矛盾。定理证毕这与前面假设矛盾。定理证毕.50引理告诉我们引理告诉我们,覆盖、独立集合、集团三者只覆盖、独立集合、集团三者只是同一个问题的不同叙述。是同一个问题的不同叙述。上述引理提供了极为简单的方法，上述引理提供了极为简单的方法，可将一个问题转换为其它两个问题。譬如

25、，可将一个问题转换为其它两个问题。譬如，欲将顶点覆盖问题转换为集团问题，只需映射欲将顶点覆盖问题转换为集团问题，只需映射 f：VC CL由由VC的实例：的实例：G(V,E)及正整数及正整数K，映射，映射f构构造造CL的实例：图的实例：图G(G的补图的补图)和和正整数正整数J|V|K51因此只要证这三个问题中一个是因此只要证这三个问题中一个是NP完全问题完全问题就证明了三个问题都是就证明了三个问题都是NP完全问题完全问题.由定理由定理2可证得定理可证得定理3。定理定理3 集团问题集团问题(CL)和独立集合问和独立集合问题题(IS)是是NP完全问题完全问题52定理定理4 哈密尔顿回路问题哈密尔顿回路问题(HC)是是NP完全问题完全问题下一节下一节 5-8给出定理的完整证明给出定理的完整证明先用定理先用定理4的结论证明巡回售货员问的结论证明巡回售货员问题题(TS)是是NP完全问题。完全问题。53定理定理5 巡回售货员问题巡回售货员问题(TS)是是NP完全问题完全问题定理定理5的证明很简单，本章第四节的例子已的证明很简单，本章第四节的例子已经证明经证明 HC TS又又TS NP是明显的，是明显的，定理定理4结论为结论为哈密尔顿问题哈密尔顿问题(HC)是是NP完全问题，完全问题，所以所以TS问题是问题是NP完全问题完全问题54

展开阅读全文