基本NP完全问题的证明.ppt

《基本NP完全问题的证明.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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表示可满足性问

2、题的实例之集合3SAT表示三可满足性问题的实例的集合。然后再证明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，只

3、须说明如何构造C′j及U′j.公式F的项Cj是因子的集合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，z

6、2，yj}，{z1，z2，⌉yj}}即C′j含两项。将Cj一个项替换为两个项.注意:这两个项穷尽一个逻辑变量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,⌉yj

7、k-4,yjk-3},{zk-1,zk,⌉yjk-3}}即C′j含(K一2)项,比

8、U′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可以

10、扩展为f′：U′→{真,假}并使公式F′为真；从而只要给诸U′j的各逻辑变量赋值保持U的逻辑变量的赋值不变,并使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

11、已经满足Cj，则不论f给yj赋什么值,都可使C′j满足15③K=3，(P9)U′j为空，且C′j只含一个项,就是Cj,已被f满足。Cj已经含三个因子,被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

12、ji-2=