After looking at textbooks and trying to derive by my own deductive abilities, I was not able to see whether polynomial solution for #P-complete problem (that is counting problem done in polynomial time) do or do not lead to polynomial solution for PSPACE problem. Can anyone show me why it has to be one or the other way?

  • 1
    $\begingroup$ This should move to computerscience stackexchange. $\endgroup$
    – Tayfun Pay
    Jan 24, 2014 at 2:52

1 Answer 1


We know that #P is included in FPSPACE (the class of function problems corresponding to PSPACE), but we currently do not know if this inclusion is proper or not. Therefore, a polynomial time algorithm for #P-complete problems does not necessarily imply a polynomial time algorithm for all problems in PSPACE.

  • 6
    $\begingroup$ To be pedantic #P is included in FPSPACE $\endgroup$ Jan 23, 2014 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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