Question Detail: The well known SAT problem is defined here for reference sake. The DOUBLE-SAT problem is defined as $qquad mathsf{DOUBLEtext{-}SAT} = {langlephirangle 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)$:
- Introduce a new variable $y$.
- 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.
