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$?
6
$\begingroup$
$\endgroup$
13
$\begingroup$
$\endgroup$
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.
answered Jun 1 '16 at 18:15
-
$\begingroup$ So what about if just P = NP, without knowing if P = PSpace? Would that imply #P problems can be solved in polynomial time? $\endgroup$ – Parry Jan 27 '17 at 22:07
-
$\begingroup$ @Parry Good question. I looked it up in Arora and Barak's Computational Complexity: A Modern Approach, and updated my answer. $\endgroup$ – Lieuwe Vinkhuijzen Apr 3 '17 at 10:18
2
$\begingroup$
$\endgroup$
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.
answered Apr 3 '17 at 11:17
