【2017年整理】§5.5 库克(Cook)定理.pptVIP

下载本文档

7
0
约2.14千字
约 9页
2017-05-09 发布于浙江
举报
版权申诉

【2017年整理】§5.5 库克(Cook)定理.ppt

1、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
4、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
5、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
6、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
7、VIP文档为合作方或网友上传，每下载1次，网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档

【2017年整理】§5.5 库克(Cook)定理

§5．5 库克(Cook)定理令U = {u1,u2,…,um}是逻辑变量的集合，f为函数 f：U → {真，假} 变量u ∈ U ，如f(u)为真，则称u为真，否则称u为假。 u和 ?u 称为U上的因子。变量u为真时，称因子u为真，因子 ?u为假；　　　　　　　　　　　　　　　变量u为假时，称因子u为假，因子?u为真。 U上的因子构成的集合C称为U上的项。项之诸因子之间有“或”的关系。项若有一个因子为真，则我们称项为真；若项的所有因子皆假，则称项为假。由U上的项构成的集合F称为U上的公式。公式的各项之间有“与”的关系。公式若有一个项为假，则我们称公式为假；若公式的所有项皆真，则称公式为真。如存在函数 f：U → {真，假} 使公式F为真，则称公式F是可满足的。可满足性问题(SAT) 实例；逻辑变量集合 U = {u1,u2,…,um}及公式F 问：是否存在函数f：Ｕ→{真，假}使公式F为真库克(Cook)定理可满足性问题是NP完全问题. (证明略去) 下面介绍几个基本的NP完全问题，它们经常帮助我们证明其它问题是NP完全问题。三可满足性问题(3SAT) 实例: 逻辑变量集合 U = {u1,u2,…,um}及公式F 且每一个项都有且只有三个因子. 问：是否存在函数f：Ｕ→ {真，假}使公式F为真。顶点覆盖问题(VC) 实例：图G＝(V，E)及正整数K 问：图G是否有K覆盖? 考虑图G＝(V，E)， V的子集V 称为G的覆盖是指: E中每条边(Vi,Vj )的两个端点至少有一个是V的元素，即 (Vi,Vj) ∈ E 蕴含着 Vi ∈ V，或 Vj ∈ V，如|V|＝K，则称V是G的K覆盖。集团问题(CL) 实例：图G＝(V，E)及正整数 J ≤ |V| 问：图G是否有元素个数不少于J的集团。 V的子集V称为G的集团是指， V中每两个节点间都有边。即 u ∈ V和v ∈ V，蕴含着 (u，v) ∈ E 哈密尔顿回路问题(简称HC) * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.