Hiérarchie alternative de l'espace

Il est connu grâce à Immerman et Szelepcsényi que si f = Ω ( log ) (même pour les fonctions constructibles non spatiales).${\rm NSPACE}(f)={\rm coNSPACE}(f)$$f=\Omega(\log)$

Dans le même article, Immerman déclare que la hiérarchie alternative de l'espace journal s'effondre, cela signifie que (la définition de la machine de turing alternée bornée et de ce qui est une hiérarchie peut être trouvée sur wikipedia ).$\Sigma_j{\rm SPACE}(\log)={\rm NSPACE}(\log)$

Existe-t-il un article sur la hiérarchie des espaces alternatifs pour ? J'ai demandé la semaine dernière à Immerman qui ne se souvenait pas d'avoir lu quelque chose comme ça. En anglais, je voudrais savoir s'il existe une preuve écrite que l'utilisation d'une langue pouvant être décidée par une machine de Turing avec j alternances peut également être décidée par une machine à turing non déterministe avec le même espace limité.$f=\Omega(\log)$$j$

Ma question est vraiment de trouver une référence, parce que je pense avoir trouvé la preuve; mais je suppose que cela peut déjà être connu.

Je devrais peut-être dire quels sont, à mon avis, les deux principaux problèmes. D'abord si , disons f = log 2 , alors il est impossible de composer en S P A C E ( f ) TM pour obtenir un S P A C E ( f ) TM, ce que l'on pourrait faire avec L O G S P A C E TM. Deuxièmement, il y a un argument pour le cas f = O ( n $f=O(n)$$f=\log^2$$SPACE(f)$$SPACE(f)$$\rm{LOGSPACE}$$f=O(n)$et un pour mais il y a encore un problème pour les fonctions qui ne sont ni O ( n ) ni Ω ( n ) .$f=\Omega(n)$$O(n)$$\Omega(n)$

Soit - S P A C E ( a ( n ) , s ( n ) ) la classe des problèmes qui peuvent être résolus avec une ( n ) alternance dans l' espace s ( n ) . À l'apogée de la théorie de la complexité parallèle, cette classe revenait assez souvent.$ALTS$$SPACE(a(n),s(n))$$a(n)$$s(n)$

Par exemple, la classe est juste A L T - S P A C E ( log n , log n ) . J'imagine donc qu'il y a beaucoup d'articles sur votre sujet, bien qu'ils ne soient peut-être pas écrits dans la notation que vous utilisez.$AC^1$$ALT$$SPACE(\log n, \log n)$

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.

More generally, the Immerman-Szelepscényi method gives that $ALTSPACE(a(n),s(n))$ est dans $NSPACE(a(n)s(n))$. L'idée de la preuve est la suivante: calculer le nombre de configurations accessibles dans la première alternance; à partir de chacun de ces états accessibles, calculer le nombre de configurations accessibles dans la deuxième alternance; et itérer$a(n)$fois revenir en arrière de façon "évidente". Chaque itération utilise uniquement$s(n)$ espace pour stocker le nombre de configurations accessibles.

La combinaison de cela avec le théorème de Savitch donne les résultats suivants:

Corollaire: $ALTSPACE(\log n, \log n)$ est dans $SPACE((\log n)^4)$. Plus généralement, un langage calculable dans l'espace polylogarithmique avec de nombreuses alternances polylogarithmiques est calculable en temps polylogarithmique déterministe.

Corollaire: De même, un langage calculable dans l'espace polynomial avec de nombreuses alternances polynomiales se trouve dans l'espace polynomial déterministe.

Je ne connais aucune référence pour ces $ALTSPACE$résultats ou s'ils ont été remarqués auparavant, ou même pour la notation. Leonard Berman [B] a utilisé la notation "$STA$"pour les classes" Espace / Temps / Alternance ".

[B] L. Berman, «La complexité des théories logiques», Théorie informatique 11 (1980) 71-77.