[Solved]: Question on SAT reduction

Problem Detail: 

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

Asked By : user2977105

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18815