Theoretical Computer Science

# Space alternating hierarchy

It is known thanks to Immerman and Szelepcsnyi that ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ if $f=\Omega(\log)$ (even for non-space constructible functions).

In the same paper, Immerman state that the logspace alternating hierarchy collapses, this means that $\Sigma_j{\rm SPACE}(\log)={\rm NSPACE}(\log)$ (the definition of the bounded alternating turing machine and of what is a hierarchy can be found on wikipedia).

Is there any paper about the alternating space hierarchy for $f=\Omega(\log)$ ? I asked last week to Immerman who did not remember reading anything like that. In english I would want to know if there is any written proof that using any language that can be decided by a Turing Machine with $j$ alternations can also be decided by a non deterministic turing maachine with the same space bound.

My question is really about finding a reference, because I think I figured out the proof; but I guess that it may already be known.

Maybe I should state what I think are the two main problems. First if $f=O(n)$, let's say $f=\log^2$, then it is impossible to compose to $SPACE(f)$ TM to obtains a $SPACE(f)$ TM, which we could do with $\rm{LOGSPACE}$ TM. Secondly, there is one argument for the case $f=O(n)$ and one for $f=\Omega(n)$ but there is still some problem for fonction which are neither $O(n)$ nor $\Omega(n)$.

## Solution

Let $ALTS$-$SPACE(a(n),s(n))$ be the class of problems which are solvable with $a(n)$ alternations in $s(n)$ space. During the heyday of parallel complexity theory, this class came up fairly often.

For example, the class $AC^1$ is just $ALT$-$SPACE(\log n, \log n)$. So I imagine there are plenty of papers about your topic, although they may not be written in the notation you are using.

For the rest of your question, I think one should be able to prove $ALTS$-$SPACE(a(n),\log n) \subseteq NSPACE(a(n) \log n)$ directly from Immerman-Szelepcsnyi.