注册 留言板
当前位置:首页 > 综合 > 其它 > 正文

算法期末作业01

来源:CSDN   发布时间: 2017-06-19   作者:u013760355   浏览次数:
摘要: Desription 8.3: STINGY SAT is the following problem: given a set of clauses (each a disjunction of literals) and an in...

Desription

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.

Solution

  • 对于任意给定的结果集,显然可以通过多项式次数的计算来证明是否符合Stingy SAT问题,在这里,通过判断每个单词可以判定为True的单词数小于或等于k,因此Stingy SAT问题属于NP问题。
  • 另外,将一个已知的NPC问题规约到Stingy SAT问题上,考虑到Stingy SAT和SAT问题的相似性,在这里,将SAT问题规约到Stingy SAT问题上。选取SAT评判公式f,而(f, k)则为Stingy SAT问题实例。
    当x为f的解时,由只有k个变量,解x中的True变量数不超过k,因此对于所有满足f评判公式的解同时也是(f,k)的解;
    当x为(f,k)的解,显然x也必然是f的解。
  • 综上,Stingy SAT时NP-complete问题


算法 算法导论 Stingy-SAT

我来说两句
评论内容:
验  证  码:
 
(网友评论仅供其表达个人看法,并不表明本站同意其观点或证实其描述。)
评论列表
已有 0 条评论(查看更多评论)
精彩专题
友情链接:
设为首页 - 加入收藏 Copyright @2016 Infocool 版权所有 粤ICP备16000626号