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

  1. 1、本文档共54页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
§5.6 基本NP完全问题的证明 定理1 三可满足问题(3SAT)是NP完全问题。 (证) 整个证明过程分成两步, 先证 3SAT∈NP, 再证明SAT ∝ 3SAT. 3SAT ∈ NP是显然的,因为很容易构造一不确定算法, 该算法第一阶段猜一个函数 f: U→{真, 假}。 然后,第二阶段检测公式F的值, 这只需将公式F中的所有因子u及?u分别用f(u)和f(u)的补替代, 即用“真”或“假”替代, 再对逻辑式求值。 容易看出,第二阶段所需时间是m和n的多项式 其中m是集合U的逻辑变量的个数, n是公式F的项的个数。 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′如下所述: U′ = U ∪ U′1 ∪ U′2 ∪ … ∪ U′n F′ = C′1 ∪ C′2 ∪ … ∪ C′n 其中C′j 是项的集合,且每一项含三个因子 因此F′也是项的集合,所以F′是公式。 由上两式可见: 逻辑变量集合U增加一些变量, 再改写公式F的每一项为项集合, 就得到三可满足问题的实例。 还需证明F′是可满足的充分必要条件为 F是可满足的。 为定义映射g,只须说明如何构造C′j 及U′j . 公式F的项Cj是因子的集合 Cj ={Z1,Z2,…,ZK } 即| Cj |=K, Cj由K个因子组成。 C′j 及U′j的构成按K的值 分四种情况讨论。 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 的四种情况 K=2, Cj ={z1 ,z2},则 U′j = {yj} 仅仅增加一个逻辑变量 C′j = { {z1,z2,yj},{z1,z2,?yj}} 即C′j含两项。 将Cj一个项替换为两个项. 注意: 这两个项穷尽一个逻辑变量yj 的两种情况 K=3, Cj ={z1 ,z2 ,z3},则 U′j = Φ 不增加逻辑变量 C′j = { {z1 ,z2 , z3}} 即C′j含一项。 K3, 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, 则含两项. 显然,映射g为3SAT问题计算一个实例所需时间为m和n的多项式。 要增加n个变量集合, 对应F中的n个项. 每个集合至多含m-3个变量, m为U中因子的个数 要把n个项改写为n个 项集合 每个集合至多含m-2个项, 每项有三个因子. 现在证明如F可满足, 则F′也可满足. 设 f: U→{真, 假} 能使F值为真。 因U是U′的子集, 只须证明f可以扩展为 f′: U′→{真, 假} 并使公式F′为真; 从而只要给诸U′j的各逻辑变量赋值 保持U的逻辑变量的赋值不变, 并使F′为真即可 因集合   (U′-U) 中的逻辑变量被划分为集合U′j , U′j中的逻辑变量仅出现在相应的C′j中, 因此只须证明, 映射f′可以逐次扩展到各集合U′j, 每次扩展使C′j中的项的值都为真. 同样分四种情况, ①K=1, 用数理逻辑的方法很容易证明C′j和Cj恒等,(P7) 即C′j的

文档评论(0)

jdy261842 + 关注
实名认证
文档贡献者

分享好文档!

1亿VIP精品文档

相关文档