对STINGY SAT问题属于NPC的简单证明

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.

简单来说,STINGY SAT(该翻译成贪婪SAT?)问题是SAT(Boolean Satisfiability Problem)的扩展,增加了一个限制:解中True的数量不能超过k个。


根据证明NPC(NP-Complete)问题的基本做法,主要需要找出从一个NPC问题规约到STINGY SAT问题的方法,在这里我直接选择了SAT进行规约

规约的方式是显而易见的:对于有\(n\)个变量的SAT的问题,其解中True的个数必然不超过\(n\)个,因此一个有\(n\)个变量的SAT可以规约成一个\(k=n\)STINGY SAT问题。

进行规约之后,根据如下证明:

  • STINGY SAT有多项式解法,那么就可以用这个解法同样在多项式时间内解决SAT问题,于是SAT不是NPC
  • 于是与SATNPC的前提矛盾。
  • 因此STINGY SAT也是NPC

证毕。