首页 > 代码库 > 8.3吝啬SAT问题

8.3吝啬SAT问题

吝啬SAT问题是这样的:给定一组子句(每个子句都是其中文字的析取)和整数k,求一个最多有k个变量为true的满足赋值——如果该赋值存在。证明吝啬SAT是NP-完全问题。

1.易知吝啬SAT的解可以在多项式时间内验证,因此属于NP问题。

2.如果我们把吝啬SAT问题中的k设置为输入的数目,那么SAT问题就可以规约到吝啬SAT问题,所以吝啬SAT问题是np-完全问题。

8.3吝啬SAT问题