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.

• STINGY SAT有多项式解法，那么就可以用这个解法同样在多项式时间内解决SAT问题，于是SAT不是NPC
• 于是与SATNPC的前提矛盾。
• 因此STINGY SAT也是NPC