World's most popular travel blog for travel bloggers.

[Solved]: Does P=NP imply polynomial solutions to #P?

, , No Comments
Problem Detail: 

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

Asked By : Ari

Answered By : Lieuwe Vinkhuijzen

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 P=PSPACE. This is a stronger statement than P=NP, because P=PSPACE implies P=NP (and hence, it is less likely).

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback