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.
Reducing multiple satisfiability to normal SAT
complexity theory;logic;satisfiability
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.