What's wrong with this proof that NP=Co-NP implies NP=PSPACE

Question

Below is a short informal proof that NP=co-NP implies NP=PSPACE. What's wrong with the proof?

Assuming NP=co-NP, an instance F of TQBF can be solved by a polynomial NDTM this way:

Non-deterministically guess the values for all the variables corresponding to existential quantifiers in F. The resulting formula F1 (with the guessed values substituted in the formula) will only have universal quantifiers, which makes F1 a Co-NP problem instance. Since NP=co-NP, there's a short certificate to verify F1's truth. Guess this short certificate too.

That is, the NDTM non-deterministically guesses two things: The values for all the variables corresponding to existential quantifiers in F, and the short certifcate for the intermediate (co-NP) instance F1.

Answer 1

A totally quantified boolean formula consists of an alternating sequence of quantifiers. This sequence is not of length 2, but arbitrarily long. That is the mistake you're making: an instance can be represented as a pair (P, phi) where phi is a propositional formula and L = (X_1, ..., X_k) is a partition of the set of variables occuring in phi, such that X_i are the variables in the i'th quantifier (which is an existential one if i is odd, and universal otherwise). You are assuming that this instance is equivalent to (L', phi), L' = (X_1', X_2') where X_1' is the union of the odd-indexed X_i, and X_2' is the union of the even-indexed X_i. Please verify for yourself that this is not necessarily true.

Answer 2

The problem is the part which you deduce "an instance F of TQBF can be solved by a polynomial NDTM" from "NP=co-NP."

Note that NP=co-NP means that you can solve the TAUTOLOGY problem using a polynomial-time NDTM, where the TAUTOLOGY problem is the following: Given a propositional formula φ, is it always satisfiable?

The TAUTOLOGY problem has nothing to do with solving the first-order formulae (such as TQBF). Even if NP=co-NP, you may not be able to solve TQBF in the way stated in the question.

Answer 3

The other answers point out correctly that you are not dealing with $TQBF$ but just a quantified boolean formula with just one alternation, i.e. the second level of polynomial hierarchy. That is not (known to be) complete for $PSpace$. But let's assume that you were doing it repeatedly, as many times as needed. It still won't work for the following reason:

Let's assume that $NP=coNP$, say $TAUT\in coNTime(p(n))$ (and $SAT\in NTime(p(n))$), where $n$ is the input size.

What you are doing is replacing the innermost quantifier and the quantifier-free part with the opposite quantifier and a new quantifier part. The size of the quantifier free part and the size of the bound on the inner most quantifier grows each time you perform the replacement. If the size of the formula and the bound on the innermost quantifier were $m$ they will become $p(m)$ after the replacement. If you repeat this $k$ times this will increase those values to $p^k(m)$ ($k$ composition of the polynomial $p$). Let $k$ be the number of times that you need to perform this replacement.

I will assume that $p$ grows faster than $n$, i.e. $\lim_{n \to \infty} \frac{p(n)}{n} > 1$.

If $k$ is constant the result will be a polynomial in $p$ and the resulting formula will be in $NP$, this is the case for the levels of polynomial hierarchy.

If $k$ grows with $n$, the result is no longer a polynomial in $n$ and therefore the resulting formula is not in $NP$. For $PSpace$, the $k$ is polynomial in $n$ so the proof will give a formula which is in $NExp$, not a formula in $NP$.