2
$\begingroup$

Let Two-Solutions-SAT be the language of Boolean formulas that have exactly two distinct satisfying assignments. Show Two-Solutions-SAT is co-NP-hard.

I know how to show that the complement of Two-Solutions-SAT is in NP, it's relatively easy to create a nondeterministic polynomial time TM that decides it.

My problem comes with reducing from SAT to the complement of Two-Solutions-SAT. I understand how to reduce from SAT to 3SAT, but in the case of 3SAT you will always have CNF's with 3 variables. With the complement of Two-Solutions-SAT, you have to somehow reduce to the case where you have 0 or 1 or >= 3 distinct satisfying assignments, and I'm not sure how to go about reducing to that.

Thanks

$\endgroup$
  • 2
    $\begingroup$ Try to build a reduction. What co-NP-hard problems do you know, that have to do with Boolean formulas? Pick one to reduce from. If you have a formula $f$ with no satisfying assignments, can you think of any way to modify it to a related formula that will have exactly two satisfying assignments? What happens if you apply that same transformation to a function $f$ that has one or more satisfying assignments -- how many satisfying assignments will the transformed formula have? I suggest spending some quality time along these lines. If you're still stuck, edit the question to show what you tried. $\endgroup$ – D.W. Dec 10 '13 at 5:59
2
$\begingroup$

Hint: For a formula $\varphi$, let $\#(\varphi)$ be the number of satisfying assignments of $\varphi$. Come up with a polytime transformation $T$ so that $\#(T(\varphi)) = \#(\varphi) + 2$.

$\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.