# Space alternating hierarchy

It is known thanks to Immerman and Szelepcsényi 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)$.

• It would be helpful if you could include a short definition of the two hierarchies you mention. – Robin Kothari Aug 23 '10 at 5:45
• missing an 's' in hierarchies – Suresh Venkat Aug 23 '10 at 6:12
• I added a link for space bounded alternation and hierarchies, and a quick definition in english of what I would likee. For the oracle hiearchie I fear a correct definition may be too long, and anyway useless since this class is equal to non deterministic logspace. – Arthur MILCHIOR Aug 23 '10 at 6:39
• the singular of hierarchies is hierarchy, btw. can you edit that ? – Suresh Venkat Aug 23 '10 at 6:40
• Edited. I fear I never did pay attention to that. – Arthur MILCHIOR Aug 23 '10 at 7:05

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-Szelepcsényi.

• Thank you; this seems really promising. I just have no clue where to began to look for such an article. The proof did not seems a trivial corollary to me because, let M be a TM in ASPACE(f,2), let M1 be the part existantial and M2 the universal part. We can not consider anymore M2 to be a coSPACE(f)=SPACVE(f) TM because we should take the input of M1 in the input tape. But yes, there is certainly something to do using directly their proof. Even if I did not though off using a number "a(n)" of alternation. Thank you again – Arthur MILCHIOR Aug 25 '10 at 4:39

More generally, the Immerman-Szelepscényi method gives that $ALTSPACE(a(n),s(n))$ is in $NSPACE(a(n)s(n))$. The proof idea is: Calculate the number of reachable configurations in the first alternation; from each such reachable state, calculate the number of reachable configurations in the second alternation; and iterate $a(n)$ times backtracking in the "obvious" fashion. Each iteration uses only $s(n)$ space to store the counts of reachable configurations.

Combining this with Savitch's theorem gives the following results:

Corollary: $ALTSPACE(\log n, \log n)$ is in $SPACE((\log n)^4)$. More generally, a language computable in polylogarithmic space with polylogarithmically many alternations is computable in deterministic polylogarithmic time.

Corollary: Similarly, a language computable in polynomial space with polynomially many alternations is in deterministic polynomial space.

I don't know any references for these $ALTSPACE$ results or whether they have been noticed before, or even for the notation. Leonard Berman[B] used the notation "$STA$" for "Space/Time/Alternation" classes.

[B] L. Berman, "The Complexity of Logical Theories", Theoretical Computer Science 11 (1980) 71-77.