§5.5 库克(Cook)定理.ppt

《§5.5 库克(Cook)定理.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、§5．5库克(Cook)定理1令U={u1,u2,…,um}是逻辑变量的集合，f为函数f：U→{真，假}变量u∈U，如f(u)为真，则称u为真，否则称u为假。u和⌉u称为U上的因子。变量u为真时，称因子u为真，因子⌉u为假；变量u为假时，称因子u为假，因子⌉u为真。2U上的因子构成的集合C称为U上的项。项之诸因子之间有“或”的关系。项若有一个因子为真，则我们称项为真；若项的所有因子皆假，则称项为假。由U上的项构成的集合F称为U上的公式。公式的各项之间有“与”的关系。公式若有一个项为假，则我们称公式为假；若公式的所有项皆真，则称公式为

2、真。如存在函数f：U→{真，假}使公式F为真，则称公式F是可满足的。3可满足性问题(SAT)实例；逻辑变量集合U={u1,u2,…,um}及公式F问：是否存在函数f：Ｕ→{真，假}使公式F为真库克(Cook)定理可满足性问题是NP完全问题.(证明略去)4下面介绍几个基本的NP完全问题，它们经常帮助我们证明其它问题是NP完全问题。5三可满足性问题(3SAT)实例:逻辑变量集合U={u1,u2,…,um}及公式F且每一个项都有且只有三个因子.问：是否存在函数f：Ｕ→{真，假}使公式F为真。6顶点覆盖问题(VC)实例：图G＝(V，E)及正

3、整数K问：图G是否有K覆盖?考虑图G＝(V，E)，V的子集V'称为G的覆盖是指:E中每条边(Vi,Vj)的两个端点至少有一个是V'的元素，即(Vi,Vj)∈E蕴含着Vi∈V'，或Vj∈V'，如

4、V'

5、＝K，则称V'是G的K覆盖。7集团问题(CL)实例：图G＝(V，E)及正整数J≤

6、V

7、问：图G是否有元素个数不少于J的集团。V的子集V'称为G的集团是指，V'中每两个节点间都有边。即u∈V'和v∈V'，蕴含着(u，v)∈E哈密尔顿回路问题(简称HC)8SAT→3SAT→VCHCCL这些问题是NP完全的证明次序:9