对于任意一个SAT问题，设其有n个变量，则该SAT问题的满足赋值中最多有n个变量赋值为true，这相当于一个输入为（S,n）的吝啬SAT问题，所以一个SAT实例可用上述方法映射到一个吝啬SAT问题。而对于任意一个吝啬SAT问题，它是SAT问题的一种特殊情况。综上，我们成功将SAT问题规约至吝啬SAT问题，所以吝啬SAT是NP-完全问题对于任意一个SAT问题，设其有n个变量，则该SAT问题的满足赋
阅读背景：
《算法概论》习题8.3 吝啬SAT
来源：互联网
对于任意一个SAT问题，设其有n个变量，则该SAT问题的满足赋值中最多有n个变量赋值为true，这相当于一个输入为（S,n）的吝啬SAT问题，所以一个SAT实例可用上述方法映射到一个吝啬SAT问题。而对于任意一个吝啬SAT问题，它是SAT问题的一种特殊情况。综上，我们成功将SAT问题规约至吝啬SAT问题，所以吝啬SAT是NP-完全问题对于任意一个SAT问题，设其有n个变量，则该SAT问题的满足赋
分享到：
