Question

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 is$\mathbf{NP}$ -complete.

Short answer

STINGY SAT is the required assignment, it has been proved that STINGY SAT is NP complete.

Step-by-step solution

Statement of  is -complete

There are steps to show the given hassle as NP (Non-deterministic polynomial) Completeness.

Take a look at whether the STINGY SAT is in “NP”

To test whether the STINGY SAT is in “NP”, first test whether or not the answer incorporates an enjoyable challenge via evaluating the system.

Moreover, check that fewer than “okay” literals are assigned with “actual” cost by means of examining the literals as soon as.

Reduce a recognized NP-whole hassle to STINGY SAT

To prove the NP-completeness, allow us to reduce SAT to STINGY SAT.

It's far supplied that in a SAT method if there is “f” with “k” variables, then it virtually chooses the for instance of STINGY SAT.

Now, its miles had to show that: “f” is a “sure-example” of SAT if and best if is a “yes-example” of STINGY SAT.

Prove

Proof:

Anticipate that “f” is a “sure-example” of SAT. There are absolutely “k” variables. Consequently, no more than “k” variables are “genuine”.

Therefore, any gratifying venture of instance “f” for SAT will also be the enjoyable venture of example for STINGY SAT.

Subsequently, is a “yes-instance” of STINGY SAT.

Count on that is a “sure-example” of STINGY SAT, then any fulfilling assignment of that example will also be gratifying undertaking of instance “f” for SAT.

Therefore, “f” is a “yes-instance” of SAT.

Because SAT is NP-Complete, the STINGY SAT is NP-Complete.