PSPACE-completeness
The TQBF language serves in complexity theory as the canonical PSPACE-complete problem. Being PSPACE-complete means that a language is in PSPACE and that the language is also PSPACE-hard. The algorithm above shows that TQBF is in PSPACE. Showing that TQBF is PSPACE-hard requires showing that any language in the complexity class PSPACE can be reduced to TQBF in polynomial time. I.e.,
This means that, for a PSPACE language L, whether an input is in L can be decided by checking whether is in TQBF, for some function that is required to run in polynomial time (relative to the length of the input) Symbolically,
Proving that TQBF is PSPACE-hard, requires specification of .
So, suppose that L is a PSPACE language. This means that L can be decided by a polynomial space deterministic Turing machine (DTM). This is very important for the reduction of L to TQBF, because the configurations of any such Turing Machine can be represented as Boolean formulas, with Boolean variables representing the state of the machine as well as the contents of each cell on the Turing Machine tape, with the position of the Turing Machine head encoded in the formula by the formula's ordering. In particular, our reduction will use the variables and, which represent two possible configurations of the DTM for L, and a natural number t, in constructing a QBF which is true if and only if the DTM for L can go from the configuration encoded in to the configuration encoded in in no more than t steps. The function, then, will construct from the DTM for L a QBF, where is the DTM's starting configuration, is the DTM's accepting configuration, and T is the maximum number of steps the DTM could need to move from one configuration to the other. We know that T = O(exp(n)), where n is the length of the input, because this bounds the total number of possible configurations of the relevant DTM. Of course, it cannot take the DTM more steps than there are possible configurations to reach unless it enters a loop, in which case it will never reach anyway.
At this stage of the proof, we have already reduced the question of whether an input formula (encoded, of course, in ) is in L to the question of whether the QBF, i.e., is in TQBF. The remainder of this proof proves that can be computed in polynomial time.
For, computation of is straightforward—either one of the configurations changes to the other in one step or it does not. Since the Turing Machine that our formula represents is deterministic, this presents no problem.
For, computation of involves a recursive evaluation, looking for a so-called "middle point" . In this case, we rewrite the formula as follows:
This converts the question of whether can reach in t steps to the question of whether reaches a middle point in steps, which itself reaches in steps. The answer to the latter question of course gives the answer to the former.
Now, t is only bounded by T, which is exponential (and so not polynomial) in the length of the input. Additionally, each recursive layer virtually doubles the length of the formula. (The variable is only one midpoint—for greater t, there are more stops along the way, so to speak.) So the time required to recursively evaluate in this manner could be exponential as well, simply because the formula could become exponentially large. This problem is solved by universally quantifying using variables and over the configuration pairs (e.g., ), which prevents the length of the formula from expanding due to recursive layers. This yields the following interpretation of :
This version of the formula can indeed be computed in polynomial time, since any one instance of it can be computed in polynomial time. The universally quantified ordered pair simply tells us that whichever choice of is made, .
Thus, so TQBF is PSPACE-hard. Together with the above result that TQBF is in PSPACE, this completes the proof that TQBF is a PSPACE-complete language.
(This proof follows Sipser 2006 pp. 310–313 in all essentials. Papadimitriou 1994 also includes a proof.)
Read more about this topic: True Quantified Boolean Formula