6
$\begingroup$

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).

$\endgroup$
  • 3
    $\begingroup$ looks like you answered your own question ! $\endgroup$ – Suresh Venkat Oct 12 '10 at 15:45
  • 1
    $\begingroup$ although technically what you just showed is that #P \subseteq FPSPACE (since you're outputting a value) $\endgroup$ – Suresh Venkat Oct 12 '10 at 15:46
  • $\begingroup$ 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. $\endgroup$ – Evgenij Thorstensen Oct 12 '10 at 15:48
  • 1
    $\begingroup$ @Evgenij: You should earn 2 new badges: Self-Answerizer and Fastest-Question-Ever-Made ;-) $\endgroup$ – Giorgio Camerani Oct 12 '10 at 15:51
  • $\begingroup$ there is an 'answered your own question' badge: I think it's called Self-Learner or something like that $\endgroup$ – Suresh Venkat Oct 12 '10 at 16:09
9
$\begingroup$

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$.

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Oct 12 '10 at 23:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Oct 13 '10 at 14:05
  • 1
    $\begingroup$ 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). $\endgroup$ – Daniel Apon Oct 13 '10 at 17:49
  • 2
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Oct 13 '10 at 19:06
  • 1
    $\begingroup$ @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.” $\endgroup$ – Tsuyoshi Ito Oct 13 '10 at 20:29

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.