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
