题目
STINGY SAT is the following problem: given a set of clauses(each a disjunction of literals) ans 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-complete SAT是归约到STINGY SAT的即可，即x是f的解当且仅当x是(f,k)的解。 对于充分性方向， 因为x是f的解，所以最多有k个变量为true，则x对于(f,k)也为真，所以充分性得证。 对于必要性方向， 因为x是（f,k）的解，x也是f的解。故必要性得证。 综上所述，STINGY SAT是NP-complete问题
