# Question on SAT reduction

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

• 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. – D.W. Dec 10 '13 at 5:59

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