<p>More generally, the Immerman-Szelepscényi method gives that <span class="math-container">$ALTSPACE(a(n),s(n))$</span> is in <span class="math-container">$NSPACE(a(n)s(n))$</span>.  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 <span class="math-container">$a(n)$</span> times backtracking in the &quot;obvious&quot; fashion.  Each iteration uses only <span class="math-container">$s(n)$</span> space to store the counts of reachable configurations.</p>
<p>Combining this with Savitch's theorem gives the following results:</p>
<p>Corollary: <span class="math-container">$ALTSPACE(\log n, \log n)$</span> is in <span class="math-container">$SPACE((\log n)^4)$</span>.  More generally, a language computable in polylogarithmic space with polylogarithmically many alternations is computable in deterministic polylogarithmic space.</p>
<p>Corollary: Similarly, a language computable in polynomial space with polynomially many alternations is in deterministic polynomial space.</p>
<p>I don't know any references for these <span class="math-container">$ALTSPACE$</span> results or whether they have been noticed before, or even for the notation.  Leonard Berman[B] used the notation &quot;<span class="math-container">$STA$</span>&quot; for &quot;Space/Time/Alternation&quot; classes.</p>
<p>[B] L. Berman, &quot;The Complexity of Logical Theories&quot;, Theoretical Computer Science 11 (1980)
71-77.</p>

CC BY-SA 4.0
2011-04-14T00:33:02.783Z
2023-08-07T08:41:52.963Z
2023-08-07T08:41:52.963Z
Sam Buss
<p>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. </p>

<p>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.</p>

<p>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. </p>

CC BY-SA 2.5
2010-08-25T04:39:47.583Z
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
CC BY-SA 2.5
2010-08-24T23:53:56.353Z
2010-08-24T23:53:56.353Z
Ryan Williams
<p>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).</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Alternating_Turing_machine#Definition">wikipedia</a>).</p>

<p>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.</p>

<p>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. </p>

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

CC BY-SA 2.5
2010-08-23T05:45:54.143Z
It would be helpful if you could include a short definition of the two hierarchies you mention.
Robin Kothari
CC BY-SA 2.5
2010-08-23T06:12:44.803Z
missing an 's' in hierarchies
Suresh Venkat
CC BY-SA 2.5
2010-08-23T06:39:20.197Z
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
CC BY-SA 2.5
2010-08-23T06:40:36.060Z
the singular of hierarchies is hierarchy, btw. can you edit that ?
Suresh Venkat
CC BY-SA 2.5
2010-08-23T07:05:53.450Z
Edited. I fear I never did pay attention to that.
Arthur MILCHIOR
<cc.complexity-theory><reference-request><space-bounded><alternating-hierarchy>
Space alternating hierarchy
Arthur MILCHIOR
# Space alternating hierarchy

(Asked by: username_0 on 2010-08-23)

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](http://en.wikipedia.org/wiki/Alternating_Turing_machine#Definition)).

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

**Tags:** cc.complexity-theory, reference-request, space-bounded, alternating-hierarchy
> **Comments:**
> **username_1**: It would be helpful if you could include a short definition of the two hierarchies you mention.  
> **username_2**: missing an 's' in hierarchies  
> **username_0**: 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.  
> **username_2**: the singular of hierarchies is hierarchy, btw. can you edit that ?  
> **username_0**: Edited. I fear I never did pay attention to that.  

---

## 2 answers

### Answer by username_4 on 2010-08-24. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_0**: 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 by username_3 on 2011-04-14. Score: 12

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.


---

