Hierarquia alternada de espaço

Sabe-se, graças a Immerman e Szelepcsényi, que se (mesmo para funções construtivas não espaciais).f = Ω ( log ${\rm NSPACE}(f)={\rm coNSPACE}(f)$$f=\Omega(\log)$

No mesmo artigo, Immerman declara que a hierarquia alternada do espaço de logs entra em colapso, isso significa que (a definição da máquina de turbulência alternada limitada e o que uma hierarquia pode ser encontrada na wikipedia ).$\Sigma_j{\rm SPACE}(\log)={\rm NSPACE}(\log)$

Existe algum artigo sobre a hierarquia de espaço alternativo para ? Na semana passada, perguntei a Immerman, que não se lembrava de ter lido algo assim. Em inglês, eu gostaria de saber se existe alguma prova escrita de que o uso de qualquer idioma que possa ser decidido por uma máquina de Turing com alternâncias de também pode ser decidido por uma máquina de turing não determinística com o mesmo espaço limitado.$f=\Omega(\log)$$j$

Minha pergunta é realmente sobre encontrar uma referência, porque acho que descobri a prova; mas acho que isso já pode ser conhecido.

Talvez eu deva declarar quais são os dois principais problemas. Primeiro, se , digamos , é impossível compor com o TM para obter um TM, o que poderíamos fazer com TM . Em segundo lugar, há um argumento para o caso e outro para mas ainda há algum problema para a função que não é nem .f = log 2 S P A C E ( f ) S P A C E ( f ) L O G S P A C E f = O ( n ) f = Ω ( n ) O ( n ) Ω ( n $f=O(n)$$f=\log^2$$SPACE(f)$$SPACE(f)$$\rm{LOGSPACE}$$f=O(n)$$f=\Omega(n)$$O(n)$$\Omega(n)$

Seja - a classe de problemas solucionáveis ​​com alternância no espaço . Durante o auge da teoria da complexidade paralela, essa classe surgiu com bastante frequência.S P A C E ( a ( n ) , s ( n ) ) a ( n ) s ( n $ALTS$$SPACE(a(n),s(n))$$a(n)$$s(n)$

Por exemplo, a classe é apenas - . Então, imagino que há muitos artigos sobre o seu tópico, embora eles não estejam escritos na notação que você está usando. A L T S P A C E ( log n , log n $AC^1$$ALT$$SPACE(\log n, \log n)$

Para o restante da sua pergunta, acho que é possível provar - diretamente da Immerman-Szelepcsényi.S P A C E ( a ( n ) , log n ) ⊆ N S P A C E ( a ( n ) log n $ALTS$$SPACE(a(n),\log n) \subseteq NSPACE(a(n) \log n)$

De maneira mais geral, o método Immerman-Szelepscényi fornece que está no . A ideia da prova é: Calcule o número de configurações alcançáveis ​​na primeira alternação; de cada estado alcançável, calcule o número de configurações alcançáveis ​​na segunda alternância; e itere vezes retrocedendo da maneira "óbvia". Cada iteração usa apenas espaço para armazenar as contagens de configurações alcançáveis.N S P A C E ( a ( n ) s ( n ) ) a ( n ) s ( n $ALTSPACE(a(n),s(n))$$NSPACE(a(n)s(n))$$a(n)$$s(n)$

Combinar isso com o teorema de Savitch fornece os seguintes resultados:

Corolário: está no . Mais geralmente, uma linguagem computável no espaço polilogarítmico com muitas alternações polilogaritmicamente é computável no tempo polilogarítmico determinístico.S P A C E ( ( log n ) 4$ALTSPACE(\log n, \log n)$$SPACE((\log n)^4)$

Corolário: Da mesma forma, uma linguagem computável no espaço polinomial com muitas alternâncias polinomialmente está no espaço polinomial determinístico.

Não conheço nenhuma referência para esses resultados do ou se eles foram notados antes ou mesmo para a notação. Leonard Berman [B] usou a notação " " para as classes "Espaço / Tempo / Alternação".S T $ALTSPACE$$STA$

[B] L. Berman, "A complexidade das teorias lógicas", Theoretical Computer Science 11 (1980) 71-77.