<p>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.</p>

CC BY-SA 3.0
2014-01-23T16:23:23.170Z
To be pedantic #P is included in FPSPACE
Marzio De Biasi
CC BY-SA 3.0
2014-01-23T15:49:55.753Z
2014-01-23T20:15:54.967Z
2014-01-23T20:15:54.967Z
Dennis Weyland
<p>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?</p>

CC BY-SA 3.0
2014-01-24T02:52:28.947Z
This should move to computerscience stackexchange.
Tayfun Pay
<cc.complexity-theory><complexity-classes>
Would polynomial solution for #P-complete problem mean polynomial solution for PSPACE problem?
commutatora1
# Would polynomial solution for #P-complete problem mean polynomial solution for PSPACE problem?

(Asked by: username_0 on 2014-01-23)

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?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: This should move to computerscience stackexchange.  

---

## 1 answers

### Answer by username_2 on 2014-01-23. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_3**: To be pedantic #P is included in FPSPACE  

---

