§5.5 库克(Cook)定理.ppt_第1页
§5.5 库克(Cook)定理.ppt_第2页
§5.5 库克(Cook)定理.ppt_第3页
§5.5 库克(Cook)定理.ppt_第4页
§5.5 库克(Cook)定理.ppt_第5页
已阅读5页，还剩4页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1,55库克(Cook)定理,2,令U=u1,u2,um是逻辑变量的集合，f为函数f：U真，假变量uU，如f(u)为真，则称u为真，否则称u为假。u和u称为U上的因子。变量u为真时，称因子u为真，因子u为假；变量u为假时，称因子u为假，因子u为真。,3,U上的因子构成的集合C称为U上的项。项之诸因子之间有“或”的关系。项若有一个因子为真，则我们称项为真；若项的所有因子皆假，则称项为假。由U上的项构成的集合F称为U上的公式。公式的各项之间有“与”的关系。公式若有一个项为假，则我们称公式为假；若公式的所有项皆真，则称公式为真。如存在函数f：U真，假使公式F为真，则称公式F是可满足的。,4,可满足性问题(SAT)实例；逻辑变量集合U=u1,u2,um及公式F问：是否存在函数f：真，假使公式F为真库克(Cook)定理可满足性问题是NP完全问题.(证明略去),5,下面介绍几个基本的NP完全问题，它们经常帮助我们证明其它问题是NP完全问题。,6,三可满足性问题(3SAT)实例:逻辑变量集合U=u1,u2,um及公式F且每一个项都有且只有三个因子.问：是否存在函数f：真，假使公式F为真。,7,顶点覆盖问题(VC)实例：图G(V，E)及正整数K问：图G是否有K覆盖?考虑图G(V，E)，V的子集V称为G的覆盖是指:E中每条边(Vi,Vj)的两个端点至少有一个是V的元素，即(Vi,Vj)E蕴含着ViV，或VjV，如|V|K，则称V是G的K覆盖。,8,集团问题(CL)实例：图G(V，E)及正整数J|V|问：图G是否有元素个数不少于J的集团。V的子集V称为G的集团是指，V中每两个节点间都有边。即uV和vV，蕴含着(u，v)E哈密尔顿回路问题(简
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论