6
$\begingroup$

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$?

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • $\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$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.