算法_NP_证明
8.3
STINGY SAT is the following problem: given a set of clauses (each a disjunction of literals) and an
integer k, find a satisfying assignment in which at most k variables are true, if such an assignment
exists. Prove that STINGY SAT is NP-complete.
证明：
由于可以在多项式时间内验证STINGY SAT的解，所以该问题属于NP问题。而将k设为所有变量的总数
时，就可以将SAT规约到STINGY SAT，因此该问题为NP完全问题。
8.8
In the EXACT 4SAT problem, the input is a set of clauses, each of which is a disjunction of exactly
four literals, and such that each variable occurs at most once in each clause. The goal is to find a
satisfying assignment, if one exists. Prove that EXACT 4SAT is NP-complete.
证明：
由于可以在多项式时间内验证EXACT 4SAT的解，因此该问题属于NP问题。为证明其NP完全性，考虑
通过将3SAT规约到EXACT 4SAT。对于任意一个3SAT实例，如果其中某个子句中包含同一个literal多次，
那么可以把这个多次出现的literal缩减为一次；如果同时包含某个literal的肯定和否定，则可以去掉它。另
外，可以在每个子句中添加一些哑变量（辅助变量，没有实际用处），这样就可以将每个子句中包含的
literal的数目增加到四个。因此，该3SAT实例可以转化为一个EXACT 4SAT问题。因此，可以证明该问
题是NP完全的。
最新文章
- android 设置textview跑马灯效果
- Convert.ChangeType不能处理Nullable类型的解决办法
- CLR via C#深解笔记五 - 事件
- mysql:mysql_query(): Unable to save result set
- 让MySQL支持中文
- iOS开发——UI篇Swift篇&UIScrollView
- Z-Stack学习笔记
- windows server 2003 系统重装蓝屏
- 利用maven中resources插件的copy-resources目标进行资源copy和过滤
- flac文件提取专辑封面手记
- 关于sscanf函数的各种详细用法
- 点击按钮，缩放图片（img.width、img.style.width、img.offsetWidth）
- java：java构造器和java方法的区别
- 18 Loader 总结
- 【原创】互联网项目中mysql应该选什么事务隔离级别
- An incompatible version [1.1.29] of the APR based Apache Tomcat Native library is installed, while Tomcat requires version [1.2.14]
- BBS论坛（九）
- JS类型
- 【LeetCode】41. First Missing Positive (3 solutions)
- Java中如何利用File类递归的遍历指定目录中的所有文件和文件夹