Space alternating hierarchy

Question

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)$.

• Robin Kothari: It would be helpful if you could include a short definition of the two hierarchies you mention.
• Suresh Venkat: missing an 's' in hierarchies
• Arthur MILCHIOR: 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.
• Suresh Venkat: the singular of hierarchies is hierarchy, btw. can you edit that ?
• Arthur MILCHIOR: Edited. I fear I never did pay attention to that.

Answer 1

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.

• Arthur MILCHIOR: 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

Answer 2

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 space.

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.

• Emil Jeřábek: $\mathsf{ALTSPACE}(\log n,\log n)$ is uniform $\mathsf{AC}^1,ドル which is actually included in $\mathsf{DSPACE}((\log n)^2)$.
• Emil Jeřábek: In fact, going through Savitch’s theorem is generally suboptimal: a direct deterministic space simulation gives space $a(n)s(n)+s(n)^2$. I gave a reference in an answer below.

Answer 3

Let me add to the answers above that $$\begin{align*} \mathsf{ALT\text-SPACE}\bigl(a(n),s(n)\bigr)&\subseteq\mathsf{ALT\text-SPACE\text-TIME}\bigl(s(n)+a(n),s(n),(s(n)+a(n))s(n)\bigr)\\ &\subseteq\mathsf{DSPACE}\bigl((s(n)+a(n))s(n)\bigr). \end{align*}$$ Interestingly, this has been known long before Immerman–Szelepcsényi: it is stated as Proposition 1 on p. 379 in Ruzzo, On uniform circuit complexity, JCSS 22:365–383 (1981); the inclusion of the first class in the last one is Theorem 4.2 in Chandra, Kozen, Stockmayer, Alternation, JACM 28(1):114–133 (1981), attributed there to Borodin (personal communication). (The bound $s(n)+a(n)$ on the number of alternations in the middle class is not stated in the source, but it comes out of the proof.)