# A question of relationships between #P and PSPACE [closed]

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?