13
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ It would be helpful if you could include a short definition of the two hierarchies you mention. $\endgroup$ – Robin Kothari Aug 23 '10 at 5:45
  • $\begingroup$ missing an 's' in hierarchies $\endgroup$ – Suresh Venkat Aug 23 '10 at 6:12
  • $\begingroup$ 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. $\endgroup$ – Arthur MILCHIOR Aug 23 '10 at 6:39
  • $\begingroup$ the singular of hierarchies is hierarchy, btw. can you edit that ? $\endgroup$ – Suresh Venkat Aug 23 '10 at 6:40
  • $\begingroup$ Edited. I fear I never did pay attention to that. $\endgroup$ – Arthur MILCHIOR Aug 23 '10 at 7:05
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Arthur MILCHIOR Aug 25 '10 at 4:39
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.