<p>It is already known that Sharp-P is contained in PSPACE. You are claiming that what you wrote shows that PSPACE is contained in Sharp-P. To do that, you would need to simulate TQBF formula with a Sharp-P oracle. What you wrote does not do that!</p>

CC BY-SA 3.0
2017-05-08T05:30:23.773Z
Controversely, we need to simulate #SAT with a TQBF formula to prove that #P is contained in PSPACE. Any paper where I can see it?
rus9384
CC BY-SA 3.0
2017-05-08T05:39:22.967Z
I'm asking this because I am implementing such code on computer (equivalent to DTM) and I'd able to solve max-TQBF (right now I am only coding an algorithm for SAT) in quadratic time. But I fail on #SAT.
rus9384
CC BY-SA 3.0
2017-05-09T05:29:42.907Z
Ah, alright, there is some difference between PSPACE and FPSPACE. #P is member of FPSPACE.
rus9384
CC BY-SA 3.0
2017-05-08T04:58:52.223Z
2017-05-08T04:58:52.223Z
Dave Schulman
<p>Let us assume there is some machine X that converts boolean formula to following form in polynomial time:</p>

<p>$$\Phi(x_1, x_2 .. x_m) = r_1(x_{i_1}, x_{j_1}, x_{k_1}) \land r_2(x_{i_2}, x_{j_2}, x_{k_2}) \ \land \ ... \ \land r_n(x_{i_n}, x_{j_n}, x_{k_n})$$</p>

<p>With following rules:</p>

<ol>
<li><p>$r_l$ is given as it's table, example: $r_5 = 01101100$.</p></li>
<li><p>No different $r$ share all 3 same literals.</p></li>
<li><p>If $\Phi(... , x_i, x_j, x_k, ...) = 0$ for fixed $x_i, x_j, x_k$ then $r_l(..x_i..) = 0$.</p></li>
</ol>

<p>What can this machine do after converting the formula? Really, if DTM has such formula as an input, following is true.</p>

<ol>
<li><p>Solve SAT in $\mathcal{O}(1)$ time. It is a consequence of third rule. If $\Phi$ is not true for any arguments, it is not true for all $r$.</p></li>
<li><p>Solve TQBF in $\mathcal{O}(n)$ time. If all $r$ are true then $\Phi$ is true. Checking all $r$ takes linear time.</p></li>
<li><p>Return certificate for (TQ)BF in $\mathcal{O}(n)$ time. You can convert any $1$ bit to a set of 3 variables in $\mathcal{O}(1)$ time using Gray code.</p></li>
</ol>

<p>What it can't do? It may be surprising.</p>

<p>It can't solve $\text{#SAT}$ in polynomial time. At least I don't know the algorithm.</p>

<p>Even if you know amount of solutions for all $r$ of non-quantified formula it doesn't give an answer.</p>

<p>Is this a proof that $PSPACE \subseteq \text{#}P$ ? And thus a much stronger theorem for $\text{#}P$ than Toda's.</p>

<p>How this will affect relationships between $PSPACE$ and $IP$ ?</p>

<p>It is known that $IP$ can solve exactly-k-#SAT. Can it answer if boolean formula has at least $k$ solutions?</p>

<cc.complexity-theory><complexity-classes><turing-machines>
A question of relationships between #P and PSPACE
rus9384
# A question of relationships between #P and PSPACE

(Asked by: username_0 on 2017-05-07)

Let us assume there is some machine X that converts boolean formula to following form in polynomial time:

$$\Phi(x\_1, x\_2 .. x\_m) = r\_1(x\_{i\_1}, x\_{j\_1}, x\_{k\_1}) \land r\_2(x\_{i\_2}, x\_{j\_2}, x\_{k\_2}) \ \land \ ... \ \land r\_n(x\_{i\_n}, x\_{j\_n}, x\_{k\_n})$$

With following rules:

1. $r\_l$ is given as it's table, example: $r\_5 = 01101100$.
2. No different $r$ share all 3 same literals.
3. If $\Phi(... , x\_i, x\_j, x\_k, ...) = 0$ for fixed $x\_i, x\_j, x\_k$ then $r\_l(..x\_i..) = 0$.

What can this machine do after converting the formula? Really, if DTM has such formula as an input, following is true.

1. Solve SAT in $\mathcal{O}(1)$ time. It is a consequence of third rule. If $\Phi$ is not true for any arguments, it is not true for all $r$.
2. Solve TQBF in $\mathcal{O}(n)$ time. If all $r$ are true then $\Phi$ is true. Checking all $r$ takes linear time.
3. Return certificate for (TQ)BF in $\mathcal{O}(n)$ time. You can convert any $1$ bit to a set of 3 variables in $\mathcal{O}(1)$ time using Gray code.

What it can't do? It may be surprising.

It can't solve $\text{#SAT}$ in polynomial time. At least I don't know the algorithm.

Even if you know amount of solutions for all $r$ of non-quantified formula it doesn't give an answer.

Is this a proof that $PSPACE \subseteq \text{#}P$ ? And thus a much stronger theorem for $\text{#}P$ than Toda's.

How this will affect relationships between $PSPACE$ and $IP$ ?

It is known that $IP$ can solve exactly-k-#SAT. Can it answer if boolean formula has at least $k$ solutions?

**Tags:** cc.complexity-theory, complexity-classes, turing-machines


---

## 1 answers

### Answer by username_1 on 2017-05-08. Score: 2

It is already known that Sharp-P is contained in PSPACE. You are claiming that what you wrote shows that PSPACE is contained in Sharp-P. To do that, you would need to simulate TQBF formula with a Sharp-P oracle. What you wrote does not do that!

> **Comments:**
> **username_0**: Controversely, we need to simulate #SAT with a TQBF formula to prove that #P is contained in PSPACE. Any paper where I can see it?  
> **username_0**: I'm asking this because I am implementing such code on computer (equivalent to DTM) and I'd able to solve max-TQBF (right now I am only coding an algorithm for SAT) in quadratic time. But I fail on #SAT.  
> **username_0**: Ah, alright, there is some difference between PSPACE and FPSPACE. #P is member of FPSPACE.  

---

