【NP问题】8.3

首先，易知 STINGY SAT 的解是可在多项式时间内验证的，因此属于 NP。另外， 很容易可以将 SAT 归约到 STINGY SAT（将k 设为所有变量的总个数即可），于是可 知 STINGY SAT 为 NP 完全问题。