TQBF is PSPACE-complete

The membership part is exactly [L1]. So it remains to prove PSPACE-hardness.

Because $L\in \mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$, there is a deterministic machine $M$ deciding $L$ in space $p(n)$ for some polynomial $p$. Fix an input $x$ of length $n$. By [L2], configurations of $M$ on $x$ can be encoded by bit strings of length $m=O(p(n))$. If $M$ has more than one accepting configuration, adjoin one fresh sink vertex $t$ and one edge from every accepting configuration to $t$; this changes the encoding length by at most one bit and preserves acceptance.

By [L3], the resulting graph has at most $2^{cp(n)}$ vertices for some constant $c$. Choose $k:=cp(n)$ large enough that $2^k$ exceeds this number, and form the quantified Boolean formula ${\mathrm{\Phi }}_x:={\mathrm{\Theta }}_k(C_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x),t)$ using [L4].

We claim that ${\mathrm{\Phi }}_x$ is true if and only if $M$ accepts $x$. The proof is by induction on the index used in [L4]. For $i=0$, ${\mathrm{\Theta }}_0(U,V)$ says exactly that $U=V$ or that one legal edge joins $U$ to $V$. For $i\ge 1$, the formula chooses a midpoint $W$ and then, by the universal choice of the selector bit $b$, forces one recursive call to certify the left half and one to certify the right half. Hence ${\mathrm{\Theta }}_i(U,V)$ is true exactly when there is a path from $U$ to $V$ of length at most $2^i$. With $U=C_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}(x)$ and $V=t$, this means exactly that $M$ accepts $x$.

By [L5], ${\mathrm{\Phi }}_x$ has polynomial size. Because the transition table of $M$ is fixed and the configuration length is polynomial, the formula ${\mathrm{\Phi }}_x$ can be written down from $x$ in polynomial time. Step 3.1 shows $x\in L⟺{\mathrm{\Phi }}_x\in \mathrm{T}\mathrm{Q}\mathrm{B}\mathrm{F}$, so by [L6] the map $x\mapsto {\mathrm{\Phi }}_x$ is a polynomial-time many-one reduction from $L$ to TQBF.

Steps 1.1 and 4.1 prove that TQBF is in PSPACE and PSPACE-hard. Therefore TQBF is PSPACE-complete.