3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

By Toda's theorem, this would imply that the entire polynomial hierarchy collapses. (So P = NP, and a lot more.) I don't know of any consequences for PSPACE.

Edit: Note that Toda's theorem is overkill here. It is immediate that your assumption implies P = NP, which in turn implies that P = PH.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Emil Jeřábek Jul 1 '15 at 13:48
  • $\begingroup$ 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. $\endgroup$ – chazisop Jul 1 '15 at 14:14
  • 3
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jul 1 '15 at 14:33
  • $\begingroup$ 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. $\endgroup$ – chazisop Jul 1 '15 at 14:42

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.