基本NP完全问题的证明.ppt
《基本NP完全问题的证明.ppt》由会员分享,可在线阅读,更多相关《基本NP完全问题的证明.ppt(54页珍藏版)》请在三一办公上搜索。
1、1,5.6 基本NP完全问题的证明,2,定理1 三可满足问题(3SAT)是NP完全问题。(证)整个证明过程分成两步,先证 3SATNP,再证明SAT 3SAT3SAT 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表示可满足性问题的实例之集合3S
2、AT表示三可满足性问题的实例的集合。然后再证明g是多项式转换。SAT的实例为集合Uu1,u2,um公式Fc1,c2,cn,其中ci(i1,2,n)是项。以U及F为输入,g为3SAT构造实例U及F如下所述:,5,U=U U1 U2 Un F=C1 C2 Cn其中Cj 是项的集合,且每一项含三个因子因此F也是项的集合,所以F是公式。由上两式可见:逻辑变量集合U增加一些变量,再改写公式F的每一项为项集合,就得到三可满足问题的实例。还需证明F是可满足的充分必要条件为F是可满足的。,6,为定义映射g,只须说明如何构造Cj 及Uj.公式F的项Cj是因子的集合 Cj Z1,Z2,ZK 即|Cj|K,Cj由K
3、个因子组成。Cj 及Uj的构成按K的值分四种情况讨论。,7,Kl,Cj z1,则Uj及Cj构造为 Uj yj1,yj2 增加两个逻辑变量而已Cjz1,yj1,yj2,z1,yj1,yj2,z1,yj1,yj2,z1,yj1,yj2 即Cj含四个项。将Cj一个项替换为四个项.注意:这四个项穷尽两个逻辑变量yj1,yj2 的四种情况,8,K2,Cj z1,z2,则 Uj yj仅仅增加一个逻辑变量 Cj z1,z2,yj,z1,z2,yj 即Cj含两项。将Cj一个项替换为两个项.注意:这两个项穷尽一个逻辑变量yj 的两种情况,9,K3,Cj z1,z2,z3,则 Uj 不增加逻辑变量 Cj z1,z
4、2,z3 即Cj含一项。,10,K3,Cj z1,z2,zk,则 Uj yj1,yj2,yjk-3,增加K-3个逻辑变量 Cj 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 即Cj含(K一2)项,比|Uj|大1。若K=4,则含两项.,若K=4,则增一个变量第一项和最后一项各含两个z(原变量)和一个y(新增变量).其余各项含一个z和两个y(其中一个是因子的非),11,显然,映射g为3SAT问题计算一个实例所需时间为m和n
5、的多项式。要增加n个变量集合,对应F中的n个项.每个集合至多含m-3个变量,m为U中因子的个数要把n个项改写为n个 项集合每个集合至多含m-2个项,每项有三个因子.,12,现在证明如F可满足,则F也可满足.设 f:U真,假能使F值为真。因U是U的子集,只须证明f可以扩展为 f:U真,假并使公式F为真;从而只要给诸Uj的各逻辑变量赋值保持U的逻辑变量的赋值不变,并使F为真即可,13,因集合(UU)中的逻辑变量被划分为集合Uj,Uj中的逻辑变量仅出现在相应的Cj中,因此只须证明,映射f可以逐次扩展到各集合Uj,每次扩展使Cj中的项的值都为真,14,同样分四种情况,K1,用数理逻辑的方法很容易证明C
6、j和Cj恒等,(P7)即Cj的值只与z1有关,因f已经满足Cj,则f不论给yj1,yj2赋什么值都能使Cj满足。,15,K=2,同样可用数理逻辑证明Cj和Cj恒等,即Cj的值只与z1,z2有关,因f已经满足Cj,则不论f给yj赋什么值,都可使Cj满足,16,K=3,(P9)Uj为空,且Cj只含一个项,就是Cj,已被f满足。Cj已经含三个因子,被f赋值,因此f,不用给任何新逻辑变量赋值。,17,K3,Cj=z1,z2,zk,因f已满足Cj,此即Cj的K个因子中至少一个为真,设zi为真,按i的值分三种情况,讨论如何扩展映射f,18,()i为1或2,则令 yj1=yj2=yjK-3=假 这使Cj的每
7、一项都为真。()如i为K4或K 3,则令 yj1=yj2=yjK-3=真 这也使Cj的每一项都为真。()如2iK4,则令 yj1=yj2=yji-2=真 yji-1=yji=yjK-3=假 这又使Cj的每一项都为真。,19,这就证明了公式F中所有的Cj都被满足,也就证明了公式F被我们构造的映射f满足。现在证明如F可满足,则F亦可满足。设存在映射 f:U真,假使公式F值为真.如何定义映射 f?,20,定义映射 f:U 真,假为 f(u)f(u)(uU)U是U的子集,如uU,则uU现在证明f满足公式F,即f使公式F的值为真。,21,此即,Cj 被满足,要证明Cj也能被满足 Kl,Cj有四项(P7)
8、这四个项穷尽两个逻辑变量yj1,yj2的四种情况 不论给yj1,yj2赋什么值,一定有某个项的后两个因子值均假,这就是说z1必定为真.所以,Cj被满足了.,22,K2,Cj有两项这两个项穷尽逻辑变量yj1的两种情况 不论给yj1赋什么值,必有一项的最后一个因子为假,这就是说z1和z2必定有一个为真.所以,Cj被满足了.,23,K3,Cj只含有一项,与Cj相同既然Cj满足了,当然Cj也满足了.,24,K3,f满足Cj,则只须证明f使 z1,z2,zk中至少有一个的值为真。用反证法.令 z1,z2,zk皆假,用“假”替代Cj中的诸z,再简化Cj 则Cj等价为,25,Cj yj1,yj1,yj2,y
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基本 NP 完全 问题 证明
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-5952191.html