<p>By definition, $\mathbb{P} = \mathbb{NP}$, since any $\mathbb{NP}$ problem could be solved by answering the question "Is the # of accepting paths non-zero", which by assumption, can be calculated in $\mathbb{P}$. As a consequence, the polynomial hierarchy collapses as well.</p>

<p>You also get other results by using results or their contrapositives.</p>

CC BY-SA 3.0
2015-07-01T13:48:18.990Z
This doesn’t sound right, the collapse of #P to P shouldn’t imply collapse of circuit classes below P. Why would the computability of permanent (the function) in polynomial time imply that permanent (the polynomial) has polynomial-size arithmetic circuits over a given field?
Emil Jeřábek
CC BY-SA 3.0
2015-07-01T14:14:52.810Z
I haven't read the result from Bürgisser's book, but it is probably related to writing the permanent as a determinant of some matrix, i.e. determinantal complexity, with some extra depth necessary for the reductions. Also note that $NC^{i}/poly$ are non-uniform versions (equiv. with advice), which I am not aware that are contained in $P$. Finally, the permanent is known to be $\#P$-complete for nonnegative matrices, which one could reduce the positive characteristic case to, if that is what you mean by the function/polynomial distinction.
chazisop
CC BY-SA 3.0
2015-07-01T14:33:18.783Z
I do have an idea how the algebraic complexity results you mention work, but the problem is you’ll never get there in the first place. You can’t simulate bitwise computation by algebraic circuits over infinite fields as then there is no way how to convert between a single field element and an unbounded sequence of bits, whereas over finite fields the simulation will only give a polynomial computing the same function, not the same polynomial, and in particular it won’t work in extension fields.
Emil Jeřábek
CC BY-SA 3.0
2015-07-01T14:42:59.070Z
Thanks, it is clear now. I was aware that the char 0 case was "problematic", but I was under the impression it should work over positive one. I'll edit the answer accordingly.
chazisop
CC BY-SA 3.0
2015-07-01T13:08:59.213Z
2015-07-01T14:44:24.997Z
2015-07-01T14:44:24.997Z
chazisop
<p>As title says what happens to other complexity classes if all $\#P$ (Sharp-P) problems have polynomial-time algorithms? What happens to PSPACE?</p>

<cc.complexity-theory><complexity-classes><conditional-results>
What happens to complexity classes if all $\#P$ problems have polynomial-time algorithms?
mute
# What happens to complexity classes if all $\#P$ problems have polynomial-time algorithms?

(Asked by: username_0 on 2015-07-01)

As title says what happens to other complexity classes if all $\#P$ (Sharp-P) problems have polynomial-time algorithms? What happens to PSPACE?

**Tags:** cc.complexity-theory, complexity-classes, conditional-results


---

## 1 answers

### Answer by username_1 on 2015-07-01. Score: 1

By definition, $\mathbb{P} = \mathbb{NP}$, since any $\mathbb{NP}$ problem could be solved by answering the question "Is the # of accepting paths non-zero", which by assumption, can be calculated in $\mathbb{P}$. As a consequence, the polynomial hierarchy collapses as well.

You also get other results by using results or their contrapositives.

> **Comments:**
> **username_2**: This doesn’t sound right, the collapse of #P to P shouldn’t imply collapse of circuit classes below P. Why would the computability of permanent (the function) in polynomial time imply that permanent (the polynomial) has polynomial-size arithmetic circuits over a given field?  
> **username_1**: I haven't read the result from Bürgisser's book, but it is probably related to writing the permanent as a determinant of some matrix, i.e. determinantal complexity, with some extra depth necessary for the reductions. Also note that $NC^{i}/poly$ are non-uniform versions (equiv. with advice), which I am not aware that are contained in $P$. Finally, the permanent is known to be $\#P$-complete for nonnegative matrices, which one could reduce the positive characteristic case to, if that is what you mean by the function/polynomial distinction.  
> **username_2**: I do have an idea how the algebraic complexity results you mention work, but the problem is you’ll never get there in the first place. You can’t simulate bitwise computation by algebraic circuits over infinite fields as then there is no way how to convert between a single field element and an unbounded sequence of bits, whereas over finite fields the simulation will only give a polynomial computing the same function, not the same polynomial, and in particular it won’t work in extension fields.  
> **username_1**: Thanks, it is clear now. I was aware that the char 0 case was "problematic", but I was under the impression it should work over positive one. I'll edit the answer accordingly.  

---

