LOGLOG = NLOGLOG?

32

Defina LOGLOG como a classe de idiomas que pode ser calculada no espaço O (loglog n) por uma máquina de Turing determinística (com acesso bidirecional à entrada). Da mesma forma, defina NLOGLOG como a classe de idiomas que pode ser calculada no espaço O (log log n) por uma máquina de Turing não determinística (com acesso bidirecional à entrada). Realmente não se sabe que essas classes diferem?

Eu só consegui encontrar algumas pesquisas mais antigas e um teorema de que se elas são iguais a L = NL (que não é apenas um argumento trivial de preenchimento!), Mas, de alguma forma, sinto que separar essas classes não pode ser tão difícil. É claro que eu posso estar completamente errado, mas se cada segundo bit da entrada são números de 1 a n em ordem crescente em binário, separados por alguns símbolos, as máquinas já podem aprender loglog n e com qualquer outro segundo bit podemos insira um problema que possa enganar uma máquina determinística, mas não uma máquina não determinística. Ainda não vejo exatamente como isso pode ser feito, mas parece uma abordagem possível, pois, com esse truque, podemos basicamente inserir um log de profundidade e uma árvore binária junto com sua estrutura, em vez da fita linear usual.

domotorp
fonte
3
Em uma pesquisa rápida, encontrei o artigo "Computing with Sublogarithmic Space" de Maciej Liskiewicz e Rudiger Reischuk. Além disso, parece que no espaço sublogarítmico, as relações de classe dependem muito do modelo usado.
Chazisop
11
@chazisop: esta é uma das pesquisas que eu também encontrei, tudo parece ter pelo menos dez anos sobre o assunto.
Domotorp
11
Acho que @Kaveh é referido neste post .
Hsien-Chih Chang,
2
Sua memória é realmente vaga, o teorema é que qualquer TM usando espaço o (log log n) deve ser regular.
Domotorp 4/12/12
4
@domotorp: ambas as declarações são teoremas, mas para você precisa de fita única. (Obviamente, para você também pode assumir uma fita, pois a tradução de fita múltipla para fita única não aumenta o espaço.) A referência que Neal Young estava procurando é: Kobayashi (1985) ( dx.doi.org/10.1016/0304-3975(85)90165-3 ) construindo fora de Hennie (1965) ( dx.doi.org/10.1016/S0019-9958(65)90399-2 ), que mostraram que as TMs de fita única de tempo linear decidem apenas idiomas regulares e introduziram seqüências cruzadas. o(nregistron)SPUMACE(o(registroregistron))
Joshua Grochow

Respostas:

15

A entrada no zoológico de complexidade é surpreendentemente detalhada; alega que NLOGLOG = co-NLOGLOG no artigo

Cálculos não determinísticos no espaço sublogarítmico e na construtibilidade espacial , Viliam Geffert, SIAM Journal on Computing, 1991.

Mas, após uma breve leitura, não vejo nenhuma alegação sobre o fato de o NLOGLOG estar fechado como complemento; talvez seja necessário um olhar mais profundo. E o principal resultado que eles têm é que não existem monótonas ilimitadas, não-construtivas e totalmente construtivas no espaço, aumentando funções para . Sabe-se que, se essas funções existirem, entãos(n)s(n)=o(registron)

SPUMACE[s(n)]NSPUMACE[s(n)] .

E, na conclusão, o autor afirmou que "... esse principal problema de separação permanece aberto ".

Como disse @chazisop, as relações dessas classes de complexidade de baixo nível dependem dos modelos, e é declarado na entrada do zoológico que

"Existem várias definições possíveis dessa classe; a mais comum é a classe de linguagens que podem ser computadas no espaço O (log log n) por uma máquina de Turing determinística com acesso bidirecional à entrada".

O que é coincidente com a sua definição e também com o artigo.

Hsien-Chih Chang 張顯 之
fonte
5
Eu acho que apenas afirma NLOGLOG = co-NLOGLOG. Também não consegui encontrar essa afirmação no resumo do artigo, embora não pudesse abrir o artigo completo.
Domotorp
2
@domotorp: Você está certo. Eu me sinto muito constrangido com a minha resposta errada ... Estou muito cansada até mesmo interpretar mal as frases, talvez eu deva fazer uma pausa no Natal.
Hsien-Chih Chang,