对于任意一个SAT问题的实例I，令I‘=(I, k)为吝啬SAT问题的一个实例，其中k=实例I的输入个数。
则对于吝啬SAT问题，实例I’若存在满足的赋值S’，那么S=S'也是SAT问题中实例I的满足赋值。
若实例I’不存在满足的赋值，则实例I也不存在满足的赋值
其中，实例I到实例I’的转换显然是多项式时间内的，且SAT问题是NP-完全问题。
因此，吝啬SAT也是NP-完全问题
