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

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?
• 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. Commented Jan 7 at 21:07

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.

• 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? Commented Jan 8 at 0:20
• @rus9384, Sorry, I don't understand what you are asking.
– D.W.
Commented Jan 8 at 4:28
• 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? Commented Jan 8 at 10:00
• @rus9384, I don't know. I don't know enough about complexity theory or Toda's theorem to answer that. Sorry.
– D.W.
Commented Jan 8 at 10:08