在进行证明之前首先给出几个相關定义：

P类npc问题实例：在一个由npc问题实例构成的集合中如果每个npc问题实例都存在多项式级复杂度的算法，这个集合就是 P 类npc问题实例

NP 类npc问題实例：能在多项式时间内检验一个解是否正确的npc问题实例NP
类npc问题实例也等价为能在多项式时间内猜出一个解的npc问题实例。这里的“猜”指的是如果有解那每次都能在很多种可能的选择中运气极佳地选择正确的一步。

NPCnpc问题实例：不同的 NP npc问题实例之间也会出现可归约的关系甚至存在这么一类（不只是一个）npc问题实例，使得任何其它的 NP
npc问题实例都能归约到它们上也就是说，能够解决它们的算法就能够解決所有其它的 NP npc问题实例这一类npc问题实例就是 NPC npc问题实例。

我们已知SATnpc问题实例是NPCnpc问题实例那么要证明Stingy SAT是NPCnpc问题实例，只需要将SATnpc问题实例归约箌Stingy SATnpc问题实例也就是说，证明解决了Stingy SATnpc问题实例就可以解决SATnpc问题实例证明如下：

给定一个SAT的npc问题实例实例I，令(I, k)为有k个变量的STINGY SATnpc问题实例实例我们可以证明，一组赋值S是I的解当且仅当S也是(I, k)的解
必要性：假设S为I的解，那么因为一共只有k个变量所以S中也有不超过k个变量可为真。所以S也是(I, k)的解
充分性：假设S是(I, k)的解，那么显然它也是对应I的解