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?


closed as unclear what you're asking by user6973, Kaveh, Jan Johannsen, Emil Jeřábek, Sasho Nikolov May 11 '17 at 5:43

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.


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!

  • $\begingroup$ 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? $\endgroup$ – rus9384 May 8 '17 at 5:30
  • $\begingroup$ 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. $\endgroup$ – rus9384 May 8 '17 at 5:39
  • $\begingroup$ Ah, alright, there is some difference between PSPACE and FPSPACE. #P is member of FPSPACE. $\endgroup$ – rus9384 May 9 '17 at 5:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.