0
$\begingroup$

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?

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

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.

$\endgroup$
  • 6
    $\begingroup$ To be pedantic #P is included in FPSPACE $\endgroup$ – Marzio De Biasi Jan 23 '14 at 16:23

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.