Largura da árvore e o problema NL vs L

31

ST-Conectividade é o problema de determinar se existe um caminho entre dois vértices dirigidos distintos e em um grafo orientado G (V, E) . Se esse problema pode ser resolvido no espaço de logs, é um problema aberto de longa data. Isso é chamado de problema NL vs L.stG(V,E)Neueu

Qual é a complexidade da conectividade ST, quando o gráfico não direcionado subjacente de G limita a largura de árvore.

É conhecido por ser NL-difícil? Existe um limite superior o(registro2n) conhecido?

Shiva Kintali
fonte

Respostas:

25

Parece que o problema está em L por [EJT10] e, portanto, é L completo sob a redutibilidade NC1 em [CM87]. Veja a página 2 de [EJT10]:

A aplicação do Teorema I.3 à fórmula ϕ(X) que expressa que X é um caminho simples de s a t mostra que o problema {(G,s,t) | tw(G)k, existe um caminho de s para t em G} está em L

Na verdade, esse resultado se aplica a todos os problemas em gráficos de largura de árvore limitada que podem ser formulados na lógica monádica de segunda ordem em L.

[EJT10] Michael Elberfeld, Andreas Jakoby e Till Tantau. Versões em espaço de log dos teoremas de Bodlaender e Courcelle. Em Anais do 51º Simpósio Anual de Fundamentos da Ciência da Computação (FOCS), páginas 143-152, 2010.

[CM87] Stephen A. Cook, Pierre McKenzie: problemas completos para o espaço logarítmico determinístico. J. Algorithms 8 (3): 385-394 (1987)

Michael Blondin
fonte