Alternating Polynomial Space with Linear Number of Alternations

A polynomial-space ATM with polynomially many alternations can be simulated in deterministic PSPACE. More generally, if $s(n)\ge\log n$ and $a(n)\ge1$, then $$\begin{align*} \mathsf{ALTSPACE}(a(n),s(n))&\subseteq\mathsf{DSPACE}\bigl(s(n)a(n)+s(n)^2\bigr),\\ \mathsf{ALTSPACE}(a(n),s(n))&\subseteq\mathsf{NSPACE}\bigl(s(n)a(n)\bigr). \end{align*}$$ The first of these is stated as Theorem 4.2 in the classic paper

A. K. Chandra, D. C. Kozen, L. J. Stockmayer: Alternation, Journal of the ACM 28 (1981), no. 1, pp. 114–133, doi 10.1145/322234.322243.

where it is attributed to Borodin; the nondeterministic improvement is a consequence of the Immerman–Szelepcsényi theorem.

To show this, the following recursive procedure can check if the ATM accepts from a given configuration $C$ using $\le a$ alternations and $\le s$ work space:

Accept(C,s,a):
    if C is in an ∃ state:
        for all space-s configurations C':
            if C' is reachable from C using only ∃ states (excluding C' itself)
               and (C' is accepting or (a>0 and Accept(C',s,a-1)))
            then ACCEPT
        REJECT
    if C is in a ∀ state:
        for all space-s configurations C':
            if C' is reachable from C using only ∀ states (excluding C' itself)
               and (C' is rejecting or (a>0 and ¬Accept(C',s,a-1)))
            then REJECT
        ACCEPT

The main deterministic part of the algorithm has recursion depth $a$, and each instance uses $O(s)$ space, hence it uses $O(sa)$ space in total.

The reachability test can be done either in nondeterministic space $O(s)$ (NB: since the test effectively appears negated in the $\forall$ case, we need here the Immerman–Szelepcsényi theorem), or in deterministic space $O(s^2)$ using Savitch’s theorem (NB: the work space of the reachability test can be reused; it does not need to be saved on each recursive invocation).