Question

7. (10 pts) 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.

Answer 1

ANSWER:

There are two steps to prove the given problem as NP (Non-deterministic polynomial) Completeness Step 1: Check whether the STINGY SAT is in "NP" To check the STINGY SAT is in "NP", first check whether the solution contains satisfying assignment by evaluating the formula. Additionally, check that fewer than "K" literals are assigned with "true" value by inspecting the literals once. Step 2: Reduce a known NP-complete problem to STINGY SAT To prove the NP-completeness, let us reduce SAT to STINGY SAT. It is provided that in a SAT formula if there is "f" with "n" variables, then it simply chooses the (f, n) as an instance of STINGY SAT Now, it is needed to prove that: "f is a "yes-instance" of SAT if and only if (f, n) is a "yes- instance" of STINGY SAT.

Proof: Assume that "f" is a "yes-instance" of SAT. There are totally "n" variables. Therefore, no more than "n" variables are "true". Therefore, any satisfying assignment of instance "f for SAT will also be the satisfying assignment of instance (f, n) for STINGY SAT Hence, (f, n) is a "yes-instance" of STINGY SAT Assume that (f, n) is a "yes-instance" of STINGY SAT, then any satisfying assignment of that instance will also be satisfying assignment of instance "f" for SAT. Hence, "f" is a "yes-instance" of SAT.