# Why solving #2SAT in polynomial time implies P = NP?

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?

• Wikipedia defines "#P" as 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. Oct 29, 2022 at 18:24
• @Dmitry thank you! it would be interesting to know how this reduction from 3SAT to #2SAT looks like Oct 29, 2022 at 20:13

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.