《算法概论》课后习题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.
要证明STINGY SAT问题是NP完全问题，可以把STINGY SAT问题转化为一个已知的NP完全问题，如SAT。
STINGY SAT和SAT的区别是，STINGY SAT规定了“satisfying assignment”中true变量的个数必须小于等于k。那么这个问题就和
变量数为k的SAT问题
是等价的，因为在析取式中，如果其中k个literal的析取为true，那么就说明整个析取式为true。这样就可以证明STINGY SAT问题是一个NP完全问题。
版权声明：本文为Liluyuan5323原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。