AFAIR, o resultado é válido apenas para limites construtíveis de espaço , não para arbitrário . f(n)≥logn
21413 Kaveh
Respostas:
8
O teorema de Immerman – Szelepcsényi trabalha sob reduções logarítmicas. Classes espaciais sublogarítmicas têm diferentes reduções. As TMs que trabalham no espaço sublogarítmico não conseguem nem registrar o comprimento da entrada . Foi demonstrado que a hierarquia de espaço para qualquer limite sublogarítmico em Ω (log log n) - o (log n) é infinita. Você pode encontrá-lo nas seguintes referências:
V. Geffert. Σ2-espaço sublogarítmico não é fechado sob complemento e outros resultados de separação . Teórica Informática e Aplicações, 27: 349-366, 1993.
M. Liśkiewicz e R. Reischuk. Separando os níveis mais baixos da hierarquia do espaço sublogarítmico . Em Anais do Simpósio sobre Aspectos Teóricos da Ciência da Computação, páginas 6–27, 1993.
B. von Braunmuhl "Alternância para máquinas de duas vias com espaço sublogarítmico ". Em Anais do Simpósio sobre Aspectos Teóricos da Ciência da Computação, páginas 5–15, 1993.
O artigo O mundo da complexidade abaixo do espaço logarítmico de M. Liśkiewicz e R. Reischuk contém um excelente resumo do espaço sublogarítmico.
Respostas:
O teorema de Immerman – Szelepcsényi trabalha sob reduções logarítmicas. Classes espaciais sublogarítmicas têm diferentes reduções. As TMs que trabalham no espaço sublogarítmico não conseguem nem registrar o comprimento da entrada . Foi demonstrado que a hierarquia de espaço para qualquer limite sublogarítmico em Ω (log log n) - o (log n) é infinita. Você pode encontrá-lo nas seguintes referências:
V. Geffert. Σ2-espaço sublogarítmico não é fechado sob complemento e outros resultados de separação . Teórica Informática e Aplicações, 27: 349-366, 1993.
M. Liśkiewicz e R. Reischuk. Separando os níveis mais baixos da hierarquia do espaço sublogarítmico . Em Anais do Simpósio sobre Aspectos Teóricos da Ciência da Computação, páginas 6–27, 1993.
B. von Braunmuhl "Alternância para máquinas de duas vias com espaço sublogarítmico ". Em Anais do Simpósio sobre Aspectos Teóricos da Ciência da Computação, páginas 5–15, 1993.
O artigo O mundo da complexidade abaixo do espaço logarítmico de M. Liśkiewicz e R. Reischuk contém um excelente resumo do espaço sublogarítmico.
fonte