<p>For the sake of completeness, let me update this answer with a direct proof. My original answer will remain below in case anyone finds it interesting. The basic idea of the direct proof is exactly as Evgenij suggests: check whether each possible assignment is satisfiable, keep a counter of satisfiable instances, and reuse space wherever possible.</p>

<p>Claim: #$P \subseteq FPSPACE$</p>

<p>Proof: Assume #$SAT$ is #$P$-complete; then it suffices to show a polynomial-space algorithm to solve #$SAT$. Here is a <em>linear</em>-space, exponential-time algorithm.</p>

<p>Initialize two counters of $k \le n$ bits to all 0, for number of variables $k$ in the $3CNF$ formula given as input. The first counter will keep track of which assignment we are checking (1 = true, 0 = false, for each variable $x_1$ to $x_k$). The second will keep track of the number of satisfying assignments (there are at most $2^k$ of them).</p>

<p>We will also need enough space ($n$ bits) to write the formula, and enough space to do "scratch work" for one clause (some very small constant number of bits, since every clause will have exactly 3 literals by definition of #$SAT$).</p>

<p>Here is the description of the algorithm:</p>

<pre>
For all possible assignments
   For all clauses in the Boolean formula
      Check if the assignment satisfies the given clause
   If the assignment satisfied every clause
      Increment the assignment counter
Output the value in the assignment counter
</pre>

<p>Note that once we finish work on one possible assignment, we don't need any information from it again to compute whether other assignments satisfy the formula; the only information we keep is <em>whether</em> it was satisfied -- in the second counter. In particular, since we can just apply binary addition of 1 to the assignment we are testing in order to always get the next assignment, and since every assignment can be checked by considering only one clause at a time (and re-using the same space for computation on every clause), the dominating factor in the space requirement is simply writing the formula itself. Alternatively, we just read from an input tape and never explicitly write the formula, then in the worst case, $k = n$ and it still takes $O(n)$ space to write the possible assignments and keep track of the number of satisfying assignments. Q.E.D.</p>

<hr>

<p>Below is my original answer:</p>

<p>Although this already essentially answered, let me give a proof of a different vein (straight out of Arora/Barak):</p>

<p>Let #$SAT_D$ = {($\phi, K$) : $\phi$ is a 3CNF formula and it has exactly $K$ satisfying assignments}</p>

<p>In Chapter 17, there is a proof that #$SAT$ is #$P$-complete.
In Chapter 8, there is a proof that #$SAT_D \in IP$.</p>

<p>Since $IP = PSPACE$, #$P \subseteq FPSPACE$.</p>

CC BY-SA 2.5
2010-10-12T23:25:02.500Z
Maybe I'm nitpicking, but #P is not a set of languages, and thus cannot be contained in PSPACE. Similarly, #SAT_D is not #P-complete, it the decision version of a problem that is #P-complete.
Robin Kothari
CC BY-SA 2.5
2010-10-13T02:11:04.257Z
You're right; it's not being too nit-picky to point that out... #P is a set of functions in the same way FP is a set of functions and P is a set of problems. I intended it in realm of someone saying "sorting is in P" and people understanding what's meant, even though sorting isn't a decision problem.
Daniel Apon
CC BY-SA 2.5
2010-10-13T14:05:53.687Z
This answer only defers the task of proving #P⊆FPSPACE to another, slightly more difficult, task of proving IP⊆PSPACE, even if we accept the use of the highly nontrivial result #SAT_D∈IP.  I would have voted this answer down if I did not encounter [a bug/misfeature in the Stack Exchange system](http://meta.stackexchange.com/questions/25488/vote-too-old-to-be-changed-again).
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-13T14:06:40.393Z
In addition, I do not think that #SAT_D is known to be #P-complete under polynomial-time Turing reducibility.  Can you point out where the claim that #SAT_D is #P-complete is stated in Arora and Barak?  (I tried to find that claim in Chapter 17 but I could not.)
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-13T17:26:50.927Z
@Tsuyoshi: $IP \subseteq PSPACE$ is relatively trivial w.r.t. $PSPACE \subseteq IP$ (at least in my opinion); i.e. just simulate an interactive proof system. Or further, let a PSPACE machine traverse the tree of all possible interactions (*by definition*, the verifier is polynomially bounded, and the number of interactions is polynomially bounded).

The relevant part of Chapter 17 is Theorem 17.10, which proves #SAT is #P-complete. My use (or abuse, depending on perspective) of terminology comes from Chapter 8, page 158 -- the two sentences following the definition of #SAT_D.
Daniel Apon
CC BY-SA 2.5
2010-10-13T17:49:48.820Z
Perhaps this is worth pointing out to the authors for inclusion in errata? The more I think about it, the more the sentence on page 158 feels a little uncomfortable (i.e. the more I agree with you).
Daniel Apon
CC BY-SA 2.5
2010-10-13T17:54:28.093Z
Either way, I've updated my answer to reflect this discussion. If you have any further thoughts, I'll be more than happy to re-visit it again.
Daniel Apon
CC BY-SA 2.5
2010-10-13T18:28:12.433Z
@Daniel: (1) Thank you for the reference to page 158, which I had not realized.  Indeed, I cannot understand what that sentence exactly means.  I agree that it is worth pointing out to the authors.  (By the way, I know that #SAT (without _D) is #P-complete.)  (2) I know that IP⊆PSPACE is much easier than IP⊇PSPACE, but that is not very relevant to my comments.  My point is that if IP⊆PSPACE is trivial, #P⊆FPSPACE is at best as trivial as that.  Therefore, I cannot see the point of proving #P⊆FPSPACE assuming IP⊆PSPACE.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-13T19:06:21.027Z
Downvoted. Two reasons: 1.) I have to agree with Tsuyoshi. Invoking more complex results to prove easier ones does not seem optimal. 2.) My previous reason: I don't like statements like #P contained in PSPACE.
Robin Kothari
CC BY-SA 2.5
2010-10-13T20:29:38.060Z
@Robin: _This_ may be a nitpicking, but I have never intended to criticize the use of the highly nontrivial result #SAT_D∈IP to prove the much easier result #P⊆FPSPACE in my comments to this answer (although I do not defend it, either).  The argument that I have made is that the answer assumes IP⊆PSPACE, which at least requires the same kind of proof as the proof of #P⊆FPSPACE.  If the answer invoked a complex result to give a proof of #P⊆FPSPACE which is _essentially different_ from the easy direct proof, I would not have said “I cannot see the point.”
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-13T22:51:46.623Z
@Robin: Ignoring the immediate discussion about IP, PSPACE, etc., I don't (necessarily) agree with your statement that using more complex (is "complex" objectively well-defined?) results to prove easier ones isn't optimal. For example, P != NP would be a very "complex" result, but surely it's extremely useful in explaining much "easier" concepts. I think it matters much less how difficult a proof is, and much more how the result of the proof lets you abstract about problems. The "logic" of the proof here is especially appealing (at least to me!) because of how elegantly the abstraction fits...
Daniel Apon
CC BY-SA 2.5
2010-10-13T22:52:50.213Z
[continued]...together. That is, if I see an interactive proof for a language, I instantly know it's in PSPACE, because IP=PSPACE. Sure, I could try to come up with a more direct and perhaps "simpler" argument that directly pertains to polynomial space requirements, but if I already know there is a valid IP system for it, do I really need to?
Daniel Apon
CC BY-SA 2.5
2010-10-13T23:00:06.290Z
A comment on my comment: I don't mean this be applied completely liberally. For instance, I think Dinur's re-proof of the PCP theorem is very useful.
Daniel Apon
CC BY-SA 2.5
2010-10-13T23:47:03.940Z
As Tsuyoshi points out, by "more complex" I meant similar but requires more work, as opposed to a completely different idea. The ideas used in proving IP in PSPACE and #P in FPSPACE are similar, but I think the latter is a much cleaner and simpler proof and doesn't require defining new concepts such as interaction.
Robin Kothari
CC BY-SA 2.5
2010-10-13T23:57:59.457Z
Fair enough. I'm actually quite sure I wouldn't have appealed to IP at all if it the series of necessary results didn't appear in Arora/Barak. On the other hand, an explicit statement of #P's relation to FPSPACE is absent from Arora/Barak. As an aside (mostly for anyone reading this thread later on), there is a description of 3SAT $\in$ PSPACE where PSPACE is defined in Arora/Barak, and the same proof immediately generalizes to #SAT, by an identical argument to the one in Evgenij's question. Oh well!
Daniel Apon
CC BY-SA 2.5
2010-10-14T02:51:38.790Z
@Daniel: Since you edited your answer in response to my objections, I have removed my downvote. A quick remark: Your proof almost exactly works even without using the #P-completeness of #SAT. I think the only change would be that you will have to use the non-deterministic machine that arises from the fact that the problem is in #P. (The one whose number of accepting paths is the answer we're trying to compute.)
Robin Kothari
CC BY-SA 2.5
2010-10-14T14:02:32.537Z
@Robin: In fact, the essence of #SAT's #P-completeness proof is a bijective mapping from certificates to assignments, so they're very similar thought processes!
Daniel Apon
CC BY-SA 2.5
2010-10-12T15:56:08.703Z
2010-10-14T01:13:45.440Z
2010-10-14T01:13:45.440Z
Daniel Apon
<p>It's obvious that NP $\subseteq$ #P. How about #P $\subseteq$ PSPACE? </p>

<p>It strikes me as semi-obvious, since we can check whether an assignment (e.g. for SAT) is a solution in polynomial time (and hence space), and since each assignment can be checked separately, we can re-use the memory needed for this check, and thus use only a polynomial amount of space to check every assignment (plus a counter to track how many of the assignments were solutions).</p>

CC BY-SA 2.5
2010-10-12T15:45:44.750Z
looks like you answered your own question !
Suresh Venkat
CC BY-SA 2.5
2010-10-12T15:46:21.533Z
although technically what you just showed is that #P \subseteq FPSPACE (since you're outputting a value)
Suresh Venkat
CC BY-SA 2.5
2010-10-12T15:48:33.940Z
I was hoping I had, but I haven't worked much with space arguments, and wanted to check whether it really is that simple. This does pave way for a future question I have.
Evgenij Thorstensen
CC BY-SA 2.5
2010-10-12T15:51:55.463Z
@Evgenij: You should earn 2 new badges: Self-Answerizer and Fastest-Question-Ever-Made ;-)
Giorgio Camerani
CC BY-SA 2.5
2010-10-12T16:09:04.937Z
there is an 'answered your own question' badge: I think it's called Self-Learner or something like that
Suresh Venkat
CC BY-SA 2.5
2010-10-12T16:18:19.133Z
Self-Learner is only awarded when one actually posts a separate answer, not when the answer is in the question.
András Salamon
CC BY-SA 2.5
2010-10-12T18:51:10.767Z
@Suresh: This technique even shows that P^{#P} is in PSPACE.
Derrick Stolee
<cc.complexity-theory><complexity-classes><space-bounded><counting-complexity>
Is #P contained in PSPACE?
Evgenij Thorstensen
# Is #P contained in PSPACE?

(Asked by: username_0 on 2010-10-12)

It's obvious that NP $\subseteq$ #P. How about #P $\subseteq$ PSPACE?

It strikes me as semi-obvious, since we can check whether an assignment (e.g. for SAT) is a solution in polynomial time (and hence space), and since each assignment can be checked separately, we can re-use the memory needed for this check, and thus use only a polynomial amount of space to check every assignment (plus a counter to track how many of the assignments were solutions).

**Tags:** cc.complexity-theory, complexity-classes, space-bounded, counting-complexity
> **Comments:**
> **username_1**: looks like you answered your own question !  
> **username_1**: although technically what you just showed is that #P \subseteq FPSPACE (since you're outputting a value)  
> **username_0**: I was hoping I had, but I haven't worked much with space arguments, and wanted to check whether it really is that simple. This does pave way for a future question I have.  
> **username_2**: @Evgenij: You should earn 2 new badges: Self-Answerizer and Fastest-Question-Ever-Made ;-)  
> **username_1**: there is an 'answered your own question' badge: I think it's called Self-Learner or something like that  
> **username_3**: Self-Learner is only awarded when one actually posts a separate answer, not when the answer is in the question.  
> **username_4**: @Suresh: This technique even shows that P^{#P} is in PSPACE.  

---

## 1 answers

### Answer by username_5 on 2010-10-12. Score: 10 | Accepted answer

For the sake of completeness, let me update this answer with a direct proof. My original answer will remain below in case anyone finds it interesting. The basic idea of the direct proof is exactly as Evgenij suggests: check whether each possible assignment is satisfiable, keep a counter of satisfiable instances, and reuse space wherever possible.
Claim: #$P \subseteq FPSPACE$
Proof: Assume #$SAT$ is #$P$-complete; then it suffices to show a polynomial-space algorithm to solve #$SAT$. Here is a linear-space, exponential-time algorithm.
Initialize two counters of $k \le n$ bits to all 0, for number of variables $k$ in the $3CNF$ formula given as input. The first counter will keep track of which assignment we are checking (1 = true, 0 = false, for each variable $x_1$ to $x_k$). The second will keep track of the number of satisfying assignments (there are at most $2^k$ of them).
We will also need enough space ($n$ bits) to write the formula, and enough space to do "scratch work" for one clause (some very small constant number of bits, since every clause will have exactly 3 literals by definition of #$SAT$).
Here is the description of the algorithm:

For all possible assignments
   For all clauses in the Boolean formula
      Check if the assignment satisfies the given clause
   If the assignment satisfied every clause
      Increment the assignment counter
Output the value in the assignment counter

Note that once we finish work on one possible assignment, we don't need any information from it again to compute whether other assignments satisfy the formula; the only information we keep is whether it was satisfied -- in the second counter. In particular, since we can just apply binary addition of 1 to the assignment we are testing in order to always get the next assignment, and since every assignment can be checked by considering only one clause at a time (and re-using the same space for computation on every clause), the dominating factor in the space requirement is simply writing the formula itself. Alternatively, we just read from an input tape and never explicitly write the formula, then in the worst case, $k = n$ and it still takes $O(n)$ space to write the possible assignments and keep track of the number of satisfying assignments. Q.E.D.

Below is my original answer:
Although this already essentially answered, let me give a proof of a different vein (straight out of Arora/Barak):
Let #$SAT_D$ = {($\phi, K$) : $\phi$ is a 3CNF formula and it has exactly $K$ satisfying assignments}
In Chapter 17, there is a proof that #$SAT$ is #$P$-complete.
In Chapter 8, there is a proof that #$SAT_D \in IP$.
Since $IP = PSPACE$, #$P \subseteq FPSPACE$.

> **Comments:**
> **username_6**: Maybe I'm nitpicking, but #P is not a set of languages, and thus cannot be contained in PSPACE. Similarly, #SAT_D is not #P-complete, it the decision version of a problem that is #P-complete.  
> **username_5**: You're right; it's not being too nit-picky to point that out... #P is a set of functions in the same way FP is a set of functions and P is a set of problems. I intended it in realm of someone saying "sorting is in P" and people understanding what's meant, even though sorting isn't a decision problem.  
> **username_7**: This answer only defers the task of proving #P⊆FPSPACE to another, slightly more difficult, task of proving IP⊆PSPACE, even if we accept the use of the highly nontrivial result #SAT_D∈IP.  I would have voted this answer down if I did not encounter [a bug/misfeature in the Stack Exchange system](http://meta.stackexchange.com/questions/25488/vote-too-old-to-be-changed-again).  
> **username_7**: In addition, I do not think that #SAT_D is known to be #P-complete under polynomial-time Turing reducibility.  Can you point out where the claim that #SAT_D is #P-complete is stated in Arora and Barak?  (I tried to find that claim in Chapter 17 but I could not.)  
> **username_5**: @Tsuyoshi: $IP \subseteq PSPACE$ is relatively trivial w.r.t. $PSPACE \subseteq IP$ (at least in my opinion); i.e. just simulate an interactive proof system. Or further, let a PSPACE machine traverse the tree of all possible interactions (*by definition*, the verifier is polynomially bounded, and the number of interactions is polynomially bounded).  The relevant part of Chapter 17 is Theorem 17.10, which proves #SAT is #P-complete. My use (or abuse, depending on perspective) of terminology comes from Chapter 8, page 158 -- the two sentences following the definition of #SAT_D.  
> **username_5**: Perhaps this is worth pointing out to the authors for inclusion in errata? The more I think about it, the more the sentence on page 158 feels a little uncomfortable (i.e. the more I agree with you).  
> **username_5**: Either way, I've updated my answer to reflect this discussion. If you have any further thoughts, I'll be more than happy to re-visit it again.  
> **username_7**: @Daniel: (1) Thank you for the reference to page 158, which I had not realized.  Indeed, I cannot understand what that sentence exactly means.  I agree that it is worth pointing out to the authors.  (By the way, I know that #SAT (without _D) is #P-complete.)  (2) I know that IP⊆PSPACE is much easier than IP⊇PSPACE, but that is not very relevant to my comments.  My point is that if IP⊆PSPACE is trivial, #P⊆FPSPACE is at best as trivial as that.  Therefore, I cannot see the point of proving #P⊆FPSPACE assuming IP⊆PSPACE.  
> **username_6**: Downvoted. Two reasons: 1.) I have to agree with Tsuyoshi. Invoking more complex results to prove easier ones does not seem optimal. 2.) My previous reason: I don't like statements like #P contained in PSPACE.  
> **username_7**: @Robin: _This_ may be a nitpicking, but I have never intended to criticize the use of the highly nontrivial result #SAT_D∈IP to prove the much easier result #P⊆FPSPACE in my comments to this answer (although I do not defend it, either).  The argument that I have made is that the answer assumes IP⊆PSPACE, which at least requires the same kind of proof as the proof of #P⊆FPSPACE.  If the answer invoked a complex result to give a proof of #P⊆FPSPACE which is _essentially different_ from the easy direct proof, I would not have said “I cannot see the point.”  
> **username_5**: @Robin: Ignoring the immediate discussion about IP, PSPACE, etc., I don't (necessarily) agree with your statement that using more complex (is "complex" objectively well-defined?) results to prove easier ones isn't optimal. For example, P != NP would be a very "complex" result, but surely it's extremely useful in explaining much "easier" concepts. I think it matters much less how difficult a proof is, and much more how the result of the proof lets you abstract about problems. The "logic" of the proof here is especially appealing (at least to me!) because of how elegantly the abstraction fits...  
> **username_5**: [continued]...together. That is, if I see an interactive proof for a language, I instantly know it's in PSPACE, because IP=PSPACE. Sure, I could try to come up with a more direct and perhaps "simpler" argument that directly pertains to polynomial space requirements, but if I already know there is a valid IP system for it, do I really need to?  
> **username_5**: A comment on my comment: I don't mean this be applied completely liberally. For instance, I think Dinur's re-proof of the PCP theorem is very useful.  
> **username_6**: As Tsuyoshi points out, by "more complex" I meant similar but requires more work, as opposed to a completely different idea. The ideas used in proving IP in PSPACE and #P in FPSPACE are similar, but I think the latter is a much cleaner and simpler proof and doesn't require defining new concepts such as interaction.  
> **username_5**: Fair enough. I'm actually quite sure I wouldn't have appealed to IP at all if it the series of necessary results didn't appear in Arora/Barak. On the other hand, an explicit statement of #P's relation to FPSPACE is absent from Arora/Barak. As an aside (mostly for anyone reading this thread later on), there is a description of 3SAT $\in$ PSPACE where PSPACE is defined in Arora/Barak, and the same proof immediately generalizes to #SAT, by an identical argument to the one in Evgenij's question. Oh well!  
> **username_6**: @Daniel: Since you edited your answer in response to my objections, I have removed my downvote. A quick remark: Your proof almost exactly works even without using the #P-completeness of #SAT. I think the only change would be that you will have to use the non-deterministic machine that arises from the fact that the problem is in #P. (The one whose number of accepting paths is the answer we're trying to compute.)  
> **username_5**: @Robin: In fact, the essence of #SAT's #P-completeness proof is a bijective mapping from certificates to assignments, so they're very similar thought processes!  

---

