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)$:
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.
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.
