# Proving DOUBLE-SAT is NP-complete

The well known SAT problem is defined here for reference sake.

The DOUBLE-SAT problem is defined as

$\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has at least two satisfying assignments}\}$

How do we prove it to be NP-complete?

More than one way to prove will be appreciated.

Here is one solution:

Clearly Double-SAT belongs to ${\sf NP}$, since a NTM can decide Double-SAT as follows: On a Boolean input formula $\phi(x_1,\ldots,x_n)$, nondeterministically guess 2 assignments and verify whether both satisfy $\phi$.

To show that Double-SAT is ${\sf NP}$-Complete, we give a reduction from SAT to Double-SAT, as follows:

On input $\phi(x_1,\ldots,x_n)$:

1. Introduce a new variable $y$.
2. Output formula $\phi'(x_1,\ldots,x_n, y) = \phi(x_1,\ldots,x_n) \wedge (y \vee \bar y)$.

If $\phi (x_1,\ldots,x_n)$ belongs to SAT, then $\phi$ has at least 1 satisfying assignment, and therefore $\phi'(x_1,\ldots,x_n, y)$ has at least 2 satisfying assignments as we can satisfy the new clause ($y \vee \bar y$) by assigning either $y = 1$ or $y = 0$ to the new variable $y$, so $\phi'$($x_1$, ... ,$x_n$, $y$) $\in$ Double-SAT.

On the other hand, if $\phi(x_1,\ldots,x_n)\notin \text{SAT}$, then clearly $\phi' (x_1,\ldots,x_n, y) = \phi (x_1,\ldots,x_n) \wedge (y \vee \bar y)$ has no satisfying assignment either, so $\phi'(x_1,\ldots,x_n,y) \notin \text{Double-SAT}$.

Therefore, $\text{SAT} \leq_p \text{Double-SAT}$, and hence Double-SAT is ${\sf NP}$-Complete.

• That's nicer than my proposal. – Raphael Oct 29 '12 at 17:35

You know that $\mathsf{SAT}$ is NP-complete. Can you find a reduction from $\mathsf{SAT}$ to $\mathsf{DOUBLE\text{-}SAT}$? That is, can you manipulate a satisfiable formula so that the result has at least two satisfying assignments? Note that the same manipulation can not render unsatisiable formulae satisfiable.

For any formula $\varphi$, the formula $\varphi \lor f(\varphi)$ has at least twice the number of satisfying assingments as $\varphi$, with $f$ a homomorphism that renames all variables to new names.