Proving DOUBLE-SAT is NP-complete

Question Detail: 

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.

Asked By : pnp

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6371

Answered By : pnp

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.