Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
The wikipedia article for #P states that if we have a polynomial-time algorithm for a #P-complete problem, P = NP is true.
As #2SAT is #P-complete, this would mean that providing a polynomial-time algorithm for #2SAT implies P = NP.
But why exactly is that? It means that there is at least one NP-complete problem that can be reduced to #2SAT right?
The Complexity of Enumeration and Reliability Problems by Leslie G. Valiant gives a series of reductions to prove that $\sharp\texttt{3SAT}\leqslant \sharp\texttt{2SAT}$. Since there is a trivial reduction from $\texttt{3SAT}$ to $\sharp\texttt{3SAT}$, you have the wanted reduction.
the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. 1) Since for any 3-SAT instance you can write a non-deterministic TM that solves this instance, by counting the number of its accepting parts (and comparing it with 0), you can solve 3-SAT. 2) This counting problem is in #P, and hence it has a reduction to #2-SAT (by #P-completeness). 3) Combining 1) and 2), you get a poly-time reduction from 3-SAT to #2-SAT. $\endgroup$