Solving 2sat #P algorithm results into P=NP

Question

So I was reading this Wikipedia article https://en.wikipedia.org/wiki/Sharp-P-complete

and stumbled on this line: How many different variable assignments will satisfy a given 2SAT formula?

Can someone link me a proof or write one that points out solving a 2SAT #P algorithm can solve any NP problem since it stated there that 2SAT#P solves PvsNP?

Answer 1

#2SAT is in P

this paper is on IPFS - this is the http-gateway:

https://gridsat.eth.limo/rc_images/abdelwahab_003_088_8_1.pdf

Answer 2

If I understand you correctly now, you are referring to this line:

A polynomial-time algorithm for solving a #P-complete problem, if it existed, would imply P = NP

in the wikipedia page you linked.

An important distinction from the title of your question is the "polynomial-time" part. A polynomail-time solution to a #p-complete problem (as #2SAT) would prove P=NP. Solutions that are not polynomial in time (in regard to their input) exist already. (I'm assuming you know that, but I feel obliged to include this clarification so people who don't know the distinction and read the question won't get misinformed).

And to answer your question - remember that #P is the class of all the counting problems corresponding to the decision problems in NP. Now from the #P Wikipedia page:

Clearly, a #P problem must be at least as hard as the corresponding NP problem. If it's easy to count answers, then it must be easy to tell whether there are any answers—just count them and see whether the count is greater than zero.

And the described reduction is of-course done in polynomial time (we are actually using the exact same input and solving the counting-problem for it, then performing one check for the output - whether it is greater than zero).

For completion of answer (again - for those who don't know it yet) here's why this shows the first quoted line is true: If there is a polynomial-time algorithm that solves a #P-complete problem, then it can be used to solve all #P problems in polynomial time by using a polynomial-time reduction from them to it (which exist as it is a #P-complete problem) and solving it with said algorithm. Showing a polynomial-time reduction for any NP problem from its corresponding #P-problem (as the second quote did) means that if such an algorithm exists, for any NP-problem we can look at its counting problem (which is in #P by definition), reduce it into #2SAT, solve it and get the result for the NP problem - all in polynomial time. Which means - if such an algorithm exists, all NP problems can be solved in polynomial-time using a deterministic Turing machine, which means they are all in P (and P=NP).