12
$\begingroup$

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.

$\endgroup$
24
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's nicer than my proposal. $\endgroup$ – Raphael Oct 29 '12 at 17:35
10
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.