Polynomial space oracle absorption

Given: the objects and hypotheses in the statement above.

Fix a total language $A\subseteq \{0,1{\}}^{\ast }$. An oracle machine writes a query word and receives its membership bit in $A$ in one answer step. Query writing counts toward time and the query tape toward space. A polynomial time clock bounds every branch for every oracle. $P^A$ and $N{P}^A$ are deterministic and nondeterministic polynomial-time oracle classes, respectively; the latter equivalently uses a polynomial-length witness and a deterministic polynomial-time $A$-oracle verifier. Use the conventions of the stated convention and the stated convention. For ${\mathrm{\Sigma }}_k^{p,A}$ and ${\mathrm{\Pi }}_k^{p,A}$, replace the deterministic predicate in the stated convention by a $P^A$ predicate; level zero is $P^A$. Define ${\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}}^A$ by deterministic polynomial space under the charged-query convention. For a language class $\mathcal{D}$, $P^{\mathcal{D}}={\bigcup }_{B\in \mathcal{D}}{P}^B$ and $N{P}^{\mathcal{D}}={\bigcup }_{B\in \mathcal{D}}N{P}^B$. Finally ${\mathrm{\Delta }}_{k+1}^p=P^{{\mathrm{\Sigma }}_k^p}$. With a fixed base oracle, a machine may query both $A$ and a language $B$; encode this by the tagged union $A\oplus B=\{0x:x\in A\}\cup \{1x:x\in B\}$. (Relativized complexity class).

The class PSPACE is the union of all deterministic polynomial-space classes: $\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}:={\bigcup }_{p\text{ polynomial}}\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(p(n))\mathrm{.}$ The class NPSPACE is the union of all nondeterministic polynomial-space classes: $\mathrm{N}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}:={\bigcup }_{p\text{ polynomial}}\mathrm{N}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(p(n))\mathrm{.}$ Equivalently, a language $L$ lies in PSPACE when there is a deterministic multitape Turing machine deciding $L$ using at most $O(n^c)$ space for some constant $c$, and similarly $L$ lies in NPSPACE when there is such a nondeterministic decider. The meanings of $\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(s(n))$ and $\mathrm{N}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(s(n))$ are those of the stated convention. (The classes PSPACE and NPSPACE).

TQBF lies in PSPACE, and every language in PSPACE polynomial-time many-one reduces to TQBF. Therefore TQBF is PSPACE-complete. (TQBF is PSPACE-complete).