基本NP完全问题的证明

基本NP完全问题的证明

ID:37570363

大小:339.10 KB

页数:54页

时间:2019-05-11

基本NP完全问题的证明_第1页
基本NP完全问题的证明_第2页
基本NP完全问题的证明_第3页
基本NP完全问题的证明_第4页
基本NP完全问题的证明_第5页
资源描述:

《基本NP完全问题的证明》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、§5.6基本NP完全问题的证明1定理1三可满足问题(3SAT)是NP完全问题。(证)整个证明过程分成两步,先证3SAT∈NP,再证明SAT∝3SAT.3SAT∈NP是显然的,因为很容易构造一不确定算法,该算法第一阶段猜一个函数f:U→{真,假}。2然后,第二阶段检测公式F的值,这只需将公式F中的所有因子u及⌉u分别用f(u)和f(u)的补替代,即用“真”或“假”替代,再对逻辑式求值。容易看出,第二阶段所需时间是m和n的多项式其中m是集合U的逻辑变量的个数,n是公式F的项的个数。3SAT∝3SAT就不那末明显了。先构造映射g:SAT→3SAT其中SAT表示可满足性问题的实例之集合3SAT

2、表示三可满足性问题的实例的集合。然后再证明g是多项式转换。SAT的实例为①集合U={u1,u2,…,um}②公式F={c1,c2,…,cn},其中ci(i=1,2,…,n)是项。以U及F为输入,g为3SAT构造实例U′及F′如下所述:4U′=U∪U′1∪U′2∪…∪U′nF′=C′1∪C′2∪…∪C′n其中C′j是项的集合,且每一项含三个因子因此F′也是项的集合,所以F′是公式。由上两式可见:逻辑变量集合U增加一些变量,再改写公式F的每一项为项集合,就得到三可满足问题的实例。还需证明F′是可满足的充分必要条件为F是可满足的。5为定义映射g,只须说明如何构造C′j及U′j.公式F的项Cj

3、是因子的集合Cj={Z1,Z2,…,ZK}即

4、Cj

5、=K,Cj由K个因子组成。C′j及U′j的构成按K的值分四种情况讨论。6K=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的四种情况7K=2,Cj={z1,z2},则U′j={yj}仅仅增加一个逻辑变量C′j={{z1,z2,yj},{z1,z2,⌉yj}}即C′j含两项。将Cj一个项替

6、换为两个项.注意:这两个项穷尽一个逻辑变量yj的两种情况8K=3,Cj={z1,z2,z3},则U′j=Φ不增加逻辑变量C′j={{z1,z2,z3}}即C′j含一项。9K>3,Cj={z1,z2,…,zk},则U′j={yj1,yj2,…,yjk-3},增加K-3个逻辑变量C′j={{z1,z2,yj1},{z3,⌉yj1,yj2},{z4,⌉yj2,yj3},…,{zi-1,⌉yji-3,yji-2},{zi,⌉yji-2,yji-1},{zi+1,⌉yji-1,yji},…,{zk-2,⌉yjk-4,yjk-3},{zk-1,zk,⌉yjk-3}}即C′j含(K一2)项,比

7、U′

8、j

9、大1。若K=4,则含两项.若K=4,则增一个变量第一项和最后一项各含两个z(原变量)和一个y(新增变量).其余各项含一个z和两个y(其中一个是因子的非)10显然,映射g为3SAT问题计算一个实例所需时间为m和n的多项式。要增加n个变量集合,对应F中的n个项.每个集合至多含m-3个变量,m为U中因子的个数要把n个项改写为n个项集合每个集合至多含m-2个项,每项有三个因子.11现在证明如F可满足,则F′也可满足.设f:U→{真,假}能使F值为真。因U是U′的子集,只须证明f可以扩展为f′:U′→{真,假}并使公式F′为真;从而只要给诸U′j的各逻辑变量赋值保持U的逻辑变量的赋值不变,并

10、使F′为真即可12因集合(U′-U)中的逻辑变量被划分为集合U′j,U′j中的逻辑变量仅出现在相应的C′j中,因此只须证明,映射f′可以逐次扩展到各集合U′j,每次扩展使C′j中的项的值都为真.13同样分四种情况,①K=1,用数理逻辑的方法很容易证明C′j和Cj恒等,(P7)即C′j的值只与z1有关,因f已经满足Cj,则f′不论给yj1,yj2赋什么值都能使C′j满足。14②K=2,同样可用数理逻辑证明C′j和Cj恒等,即C′j的值只与z1,z2有关,因f已经满足Cj,则不论f给yj赋什么值,都可使C′j满足15③K=3,(P9)U′j为空,且C′j只含一个项,就是Cj,已被f满足。C

11、j已经含三个因子,被f赋值,因此f,不用给任何新逻辑变量赋值。16④K>3,Cj={z1,z2,…,zk},因f已满足Cj,此即Cj的K个因子中至少一个为真,设zi为真,按i的值分三种情况,讨论如何扩展映射f17(ⅰ)i为1或2,则令yj1=yj2=…=yjK-3=假这使C′j的每一项都为真。(ⅱ)如i为K-4或K-3,则令yj1=yj2=…=yjK-3=真这也使C′j的每一项都为真。(ⅲ)如2

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。