Limites inferiores apertados no teorema de Savitch

28

Antes de mais, peço desculpas antecipadamente por qualquer estupidez. Eu não sou de modo algum um especialista em teoria da complexidade (longe disso! Eu sou um estudante de graduação da minha primeira aula em teoria da complexidade) Aqui está minha pergunta. Agora, o Teorema de Savitch afirma que Agora estou curioso para saber se esse limite inferior foi apertado, isto é, algo como não é possível. NSPACE ( f ( n ) )DSPACE ( ( f ( n ) ) 1.9 )

NSPACE(f(n))DSPACE((f(n))2)
NSPACE(f(n))DSPACE((f(n))1.9)

Parece que deve haver um argumento combinatório direto a ser feito aqui - cada nó no gráfico de configuração de uma máquina de Turing Deterministic possui apenas uma borda de saída, enquanto cada nó no gráfico de configuração de uma máquina de Turing não determinística pode ter mais de uma borda de saída. O que o algoritmo de Savitch está fazendo é converter gráficos de configuração com qualquer número de aresta de saída em gráficos de configuração com arestas de saída.<2

Como o gráfico de configuração define uma TM exclusiva (não tenho certeza disso), o tamanho combinatório da última é quase certamente maior que a anterior. Essa "diferença" é talvez um fator de , talvez menos - eu não sei. Obviamente, existem muitos pequenos problemas técnicos a serem resolvidos, como como você precisa garantir que não haja loops e assim por diante, mas minha pergunta é se essa é uma maneira razoável de começar a provar algo assim. n2

gabgoh
fonte

Respostas:

28

Esta é uma questão em aberto bem conhecida. Você verá na teoria da complexidade muitas questões abertas para as quais se perguntaria como é que ninguém conseguiu resolvê-las. Parte do motivo é que precisamos de novas pessoas como você para nos ajudar a resolvê-las :)

Para obter o resultado mais recente nessa área, mostrando que o algoritmo de Savitch é ideal em algum modelo restrito, consulte o documento FOCS de Aaron Potechin .

Especificamente, ele parte da boa observação de que, como o gráfico de configuração de uma TM determinística tem apenas uma borda de saída (após a fixação da entrada), pode-se pensar nele como um gráfico não direcionado, e assim a pergunta se torna algo como o seguinte: um grafo orientado de n vértices com dois vértices especiais s , t , se mapeia a um N vértice undirected gráfico G ' (também com vértices especiais s ' , t ' ) de tal modo que a existência de cada uma das arestas em G ' depende uma aresta em G e existe um caminho de sGns,tNGs,tGGspara em G se houver um caminho entre s ' e t ' em G ' , quanto maior N deve ser a partir de n .tGstGNn

To show that Savitch's algorithm is optimal, one needs to show that N has to be at least 2Ω(log2n)=nΩ(logn). To show LNL, it suffices to show the weaker bound that N>nc for every constant c. I'm pretty sure that even N>n10 is not known, though perhaps something like Nn2 is known for some not so interesting reasons.

Boaz Barak
fonte
20

Acho que não sabemos se isso é apertado. Caso contrário, saberia que .LNL

Karolina Sołtys
fonte
bom ponto, obrigado :) Na segunda pergunta - você vê alguma falha óbvia na abordagem combinatória de mostrar algo assim?
gabgoh
2
O teorema de Savitch é um algoritmo específico para simular um algoritmo não-determinístico do espaço f (n), usando dividir e conquistar com uma profundidade O (f (n)) (fornecendo f (n) ^ 2). Provar limites mais baixos envolve mostrar que TODOS os algoritmos que usam menos espaço falham em algumas entradas. É por isso que L = NL é difícil (e P = NP é difícil).
Derrick Stolee
1
Não sabemos se é apertado no sentido de que não sabemos que 2 é o melhor que podemos fazer, mas isso não significa que não sabemos . NSpace(f(n))DSpace((f(n))1.9)
Kaveh
1
Bem, nós não. Qualquer melhoria (mesmo para específico , como log n ) seria um grande avanço. flogn
Derrick Stolee
1
@Derrick Stolee: Você está perdendo o ponto do meu comentário. Apenas sabendo resposta positiva implicaria que , o argumento de Carolina não dá qualquer evidência para a dificuldade de saber uma resposta negativa, ou seja, knwoing N S p um c e ( f ( n ) ) D S p um c e ( ( f ( n ) ) 1.9 ) parece não ajudar com LLNLNSpace(f(n))DSpace((f(n))1.9)L vs . NL
Kaveh