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问题。而将k设为所有变量的总数
时，就可以将SAT规约到STINGY SAT，因此该问题为NP完全问题。
8.8
In the EXACT 4SAT problem, the input is a set of clauses, each of which is a disjunction of exactly
four literals, and such that each variable occurs at most once in each clause. The goal is to find a
satisfying assignment, if one exists. Prove that EXACT 4SAT is NP-complete.
证明：
由于可以在多项式时间内验证EXACT 4SAT的解，因此该问题属于NP问题。为证明其NP完全性，考虑
通过将3SAT规约到EXACT 4SAT。对于任意一个3SAT实例，如果其中某个子句中包含同一个literal多次，
那么可以把这个多次出现的literal缩减为一次；如果同时包含某个literal的肯定和否定，则可以去掉它。另
外，可以在每个子句中添加一些哑变量（辅助变量，没有实际用处），这样就可以将每个子句中包含的
literal的数目增加到四个。因此，该3SAT实例可以转化为一个EXACT 4SAT问题。因此，可以证明该问
题是NP完全的。
