Does P=NP imply polynomial solutions to #P?

Question

Is it true that $\#P$-complete problems could possibly be solved in polynomial time if P=NP? I know that even some counting problems related to polynomial time decision problems are $\#P$-complete, so even if P=NP it may not necessarily be true. My confusion is over how we write the answer to a $\#P$-complete problem since it may be exponential in the size of the input (for example up to $2^n$ truth assignments to a SAT instance on $n$ variables). Therefore, I cannot understand how, even if we find a fast way for computing something like the permanent of a matrix, we could still expect to write the answer in polynomial time. Am I missing something about the definition of $\#P$?

Answer 1

Your confusion is that the class #P only asks you to count the solutions, not to enumerate them, and you only need $n$ bits to write down the number $2^n$. This means that to express the number of satisfying assignments to a formula of $n$ variables, you need $n$ bits, because there are at most $2^n$ solutions (i.e. in the case of a tautology). Another example: the number of isomorphisms between two graphs is at most $n!$, which requires $\log(n!)\approx n\cdot \log(n)$ bits to write down. All these number of bits are polynomial in the size of the input

#P can be solved in polynomial time if and only if P=PP. This is a stronger statement than P=NP, because P=PP implies P=NP (and hence, it is less likely). If P=NP, then all #P problems can be approximated to within a constant factor by a deterministic algorithm.

Answer 2

P$\,=\,$NP does not imply that P$\,=\,$#P (or, more properly, FP$\,=\,$#P). We already know that there are decision problems in P whose counting versions are #P-complete, such as perfect matchings.