Does espera por ?

7

Sabe-se que para , .f(n)lognNSPACE(f(n))=coNSPACE(f(n))

E se ? Eles também são iguais?f(n)<logn

URL87
fonte
11
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.

Reza
fonte