By the winning instruction I mean a string that a deterministic polynomial time Turing machine can use in order to win the opponent in a competitive game. The difference from a certificate is that the winning instruction does not have to prove its own correctness, you just trust it.

A naive winning instruction for TQBF would look like:

If the opponent has assigned $y_i=0$ then go to the line $a$, otherwise go to the line $b$.

The naive instruction would not be reusing the lines. I.e., say, it would say to go to line 2 if the opponent has assigned $y_1=1$ and to line 3 otherwise. Then the line 2 would tell to go to line 4 if the opponent has assigned $y_2=1$ and line 5 otherwise. Meanwhile, the line 3 would tell to go to lines 6 and 7 respectively. For $y_3$ you'd need lines 8 to 15. So, the amount of lines doubles with each variable which means such an instruction would have an exponential size.

A simple complexity class that has polynomial size winning instructions is $\Sigma_2^{\mathsf{FP}}$. Suppose a quantified boolean formula $\exists X\forall Y:\varphi(X,Y)$ is true. Then a partial assignment $p(X)$ that turns the formula into a tautology would be the winning instruction.

On the other hand, it seems that $\Pi_2^{\mathsf{FP}}$ has no such winning instruction: there are exponentially many different formulas that could be produced by the opponent.

Now, suppose a formula $\exists X\ \text{Maj}(Y):\varphi(X,Y)$. Assuming it is true, the winning instruction would be a partial assignment $p(X)$ that produces a formula $\text{Maj}(Y):\varphi'(Y)=1$. This means that $\mathsf{FNP^{PP}}$ also has polynomial sized winning instructions.

However, there does not seem to be a similar construction for TQBF. It's clear that the existence of polynomial sized winning instructions is necessary for $\mathsf{PSPACE\subset NP}/poly$, however it seems far from sufficient.

So, there would be two questions here:

  1. Is it an open problem whether TQBF has polynomial sized winning instructions?
  2. If yes, then what would be the consequences of that?
  • $\begingroup$ Yes, a winning instruction, of course, only exists only if the formula is true. Just as how in case of SAT a certificate exists only if the formula is satisfiable. $\endgroup$
    – rus9384
    Commented Jan 7 at 21:07

1 Answer 1


Most likely TQBF, and even 2QBF, has no winning instruction.

Let $f:\{0,1\}^* \to \{0,1\}^*$ be a one-way permutation (OWP). Though we have no proof, it is believed/conjectured that OWPs exist. In particular, under reasonable cryptographic assumptions, one can construct a OWP.

Now consider a formula of the form

$$\forall X \exists Y . f(Y)=X,$$

where $X,Y$ are boolean vectors of length $n$. This formula is true, since $f$ is a permutation on $\{0,1\}^n$; but there is no polynomial-length winning instruction (any such winning instruction would provide a polynomial-time algorithm to invert $f$, contradicting the assumption that $f$ is one-way).

This is not yet an instance of TQBF, because there is no guarantee that there is a concise boolean expression for $f$. But you can build a boolean circuit for $f$, and then use the Tseitin transform to construct a 3CNF formula $\varphi$ such that $f(Y)=X$ iff $\exists Z . \varphi(X,Y,Z)$.

Therefore, the formula

$$\forall X \exists Y \exists Z . \varphi(X,Y,Z)$$

has no winning instructions (under the assumption that $f$ is a OWP). This formula is in TQBF. In fact, since you can absorb $Y,Z$ into a single boolean vector $Y'=(Y,Z)$, it is in 2QBF, since it has the form $\forall X \exists Y' . \varphi(X,Y')$.

Or, another way to put it is that if TQBF has winning instructions, then one-way permutation do not exist.

  • $\begingroup$ I suppose Toda's theorem does not imply that a reduction from a 2-QBF to a $FNP^{PP}$ formula (like in the post) can help with the original problem? $\endgroup$
    – rus9384
    Commented Jan 8 at 0:20
  • $\begingroup$ @rus9384, Sorry, I don't understand what you are asking. $\endgroup$
    – D.W.
    Commented Jan 8 at 4:28
  • $\begingroup$ By Toda's theorem the entire $PH$ is within $NP^{PP}$, i.e. you could reduce any k-QBF to a formula of the form $\exists X\ \text{Maj}(Y):\varphi(X,Y)$ and those formulas have polynomial sized winning instructions. However, I suppose there is no polynomial time deterministic way to decode this winning instruction into a winning instruction for the original k-QBF? $\endgroup$
    – rus9384
    Commented Jan 8 at 10:00
  • $\begingroup$ @rus9384, I don't know. I don't know enough about complexity theory or Toda's theorem to answer that. Sorry. $\endgroup$
    – D.W.
    Commented Jan 8 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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