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?


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.