I have to prove the NP-completeness of the following set: QUADRUPLE-SAT:={F is Formula in CNF|F has at least 4 satisfying interpretations}

My idea so far has been to reduce the problem to the normal SAT by constructing a new formula, copying the original formula 4 times and using a new set of literals in every copy, then adding clauses to ensure that the 4 sets of literals are pairwise differently interpreted (there is at least 1 literal which is flipped). Such a formula is easy to find, I'm unable to get it to CNF though.

I might also be on the completely wrong track on this one, if you know another NP-complete problem this could be reduced to more easily, that would be great as well.

  • 3
    $\begingroup$ Try to prove that your reduction works – this is how you can tell whether you're on the right track. You don't need us for that. $\endgroup$ – Yuval Filmus Dec 2 '16 at 23:26

CNF-SAT can be reduced to QUADRUPLE-SAT by adding two new variables, $x_1$ and $x_2$, and adding the following CNF clauses.

$(x_1 \lor \lnot x_1)$

$(x_2 \lor \lnot x_2)$

Because $x_1$ and $x_2$ can take any value and not affect satisfiability, if the original formula had at least one solution then the new formula will have at least four. And if the original formula had no solutions then the new formula will still have none.

Since CNF-SAT is NP-complete, then this reduction to QUADRUPLE-SAT proves the NP-completeness of the QUADRUPLE-SAT.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.