题目：
吝啬SAT问题是这样的：给定一组子句（每个子句都是其中文字的析取）和整数k，求一个最多有k个变量为true的满足赋值——如果该赋值存在。证明吝啬SAT是NP-完全问题。
解答：
首先我们要证明吝啬SAT问题是np-完全问题，我们首先要证明吝啬SAT问题是np问题，然后如果能把SAT问题规约到吝啬SAT问题，那么我们就能证明这个问题。
证明吝啬SAT问题为NP问题。 若已知某个与吝啬SAT问题变量对应的真值集合，可在多项式时间内将该集合带入吝啬SAT问题验证是否为解。故吝啬SAT问题为NP问题。
证明吝啬SAT为NP-完全问题。 SAT -> 吝啬SAT 令SAT问题中变量个数为k即得到吝啬SAT问题，此归约过程需要多项式时间。又因为SAT问题为已知的NP-完全问题，则吝啬SAT问题亦为NP-完全问题。
