《算法概论》第八章的一些课后题目 关于NP-Complete Problem
8.3 STINGY SAT
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.
当我们有多项式时间算法解决SAT问题时,我们可以直接解决STINGY SAT
我们取k为变量的个数,如果我们找到了多项式时间的算法解决它,也就是解决了SAT问题。验证答案是显然快速的。
我们成功将SAT归约到了STINGY SAT 证明了 STINGY SAT 是NP-Complete problem
8.14 K-clique problem
Prove that the following problem is NP-complete:given an undirected graph G=(V,E) and an integer k,
return a clique of size k as well as an independent set of size k,provided both exist.
首先,团和独立集是两个相对的概念,寻找k个元素的团和寻找k个元素的独立集是等价命题,这里不展开说明了。
书中已经给出了由3-SAT归约到k-独立集的证明,这里简单叙述一下
对于任意一个有k个clause的3SAT表达式,我们对于每个clause构造一个三点三边呈现三角形的子图,(共有k个三角形)
对于每个变量,两种相反的形式之间连一条边,如果能够找到k个元素的独立集,必然k个点分布在k个三角形,即选择了k个变量,使得表达式满足。验证满足性显然是快速的。
于是,当我们有多项式时间算法解决k独立集问题时,我们就一定有多项式时间算法解决3SAT问题,所以k独立集问题是NP-complete problem.
同样的,k独立集的等价命题 k-clique问题也是NP-complete的。
补充一道有趣的题目 ZOJ1492
该题给定我们一个无向图,求最大团的点数是多少。图的规模小于等于50
这道题我找到了搜索的解法,但是我还没想到办法严格的分析这个dfs的复杂度,但是由于dfs不是记忆化的,所以我猜想它应该是指数复杂度的。
事实上要实现dfs的记忆化,就不得不用指数级的空间来储存数据,这也是无法接受的。
不过这道题的搜索剪枝技巧性还是很强的,毕竟指数级的算法能解决50的规模,已经很不错了。
最新文章
- springMVC、httpClient调用别人提供的接口!!!(外加定时调用)
- jquery判断div是否隐藏实例
- 与你相遇好幸运,Sails.js自定义responses
- 天朝专用- 配置pypi镜像
- CodeForces 505B Mr. Kitayuta's Colorful Graph
- TortoiseGit使用与操作
- OpenGL 3:画圆
- schtasks命令遇见ERROR: The request is not supported.
- Applied Functional Analysis(Applications to Mathematical Physics ) E.Zeidler
- Knockout应用开发指南 第三章:绑定语法(3)
- 读改善c#代码157个建议:建议1~3
- shell 命名管道,进程间通信
- HDOJ2000-ASCII码排序
- Hibernate第一篇【介绍Hibernate,简述ORM,快速入门】
- 基于NIO和BIO的两种服务器对比
- 排序算法(sorting algorithm) 之 选择排序(selection sort)
- [转]BTC手续费计算,如何设置手续费
- 六招让你的Ubuntu马上提速
- c#设计模式3抽象工厂模式(Abstract Factory)
- shell脚本练习【转】