What would be the consequences of TQBF having polynomial length winning instructions?

Question

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?

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.