Algoritmos SC ^ 2 para conectividade st

15

Savitch deu um algoritmo determinístico para resolver a conectividade st usando espaço, implicando N L D S P A C E ( log 2 n ) . O algoritmo de Savitch é executado no tempo 2 O ( log 2 n ) . É um grande problema em aberto se a conectividade st pode ser resolvida por um algoritmo determinístico em tempo polinomial e espaço O ( log 2 n ) , isto é, se NO(log2n)NLDSPACE(log2n)2O(log2n)O(log2n) . R L , que se encontra entre L e N G , ésabidoestar em S C 2 . Portanto, a acessibilidade em gráficos direcionados com tempo de mistura polinomial é em S C 2 .NLSC2RLLNLSC2SC2

Estou procurando casos especiais de conectividade st (que não são conhecidos por estarem em ) que possuem algoritmos S C 2 . Sabe-se algo sobre gráficos planares, DAGs planares? Observe que a conectividade st nos DAGs permanece completa em NL.euSC2

Shiva Kintali
fonte

Respostas:

10

Existem duas classes de complexidade relacionadas no que também estão no LogDCFL , que as colocam no SC 2 (por Cook ). NLLogDCFLSC2

  • O primeiro é o , para "Espaço de log inequívoco de alcance", que tem acessibilidade em manguezais (gráficos em que cada par de vértices tem no máximo um caminho direcionado entre eles) como um problema completo. Esta classe já foi discutida antes .RUL
  • O segundo é , que tem acessibilidade completa para gráficos com no máximo um número polinomial de caminhos entre qualquer par de vértices.ReachFewL

A realização de uma pesquisa profunda desses gráficos usando uma pilha garante que levará tempo polinomial, portanto, essas classes estão no .LogDCFLSC2

Derrick Stolee
fonte
@Derrick: Por favor, adicione as referências que mostram que esses problemas estão no LogDCFL.
Shiva Kintali 7/10/10
@ Shiva: Eu pensei que o último parágrafo era um argumento de que esses problemas podem ser reconhecidos por um autômato de pushdown determinístico determinado pelo gráfico?
András Salamon
11
@Derrick: Obrigado. Portanto, há problemas na interseção de NL e LogDCFL que não são conhecidos por estar no espaço de log. Interessante !!
Shiva Kintali
2
Sim, muito interessante. Novamente, os manguezais têm o fator (log log n) de eficiência de espaço sobre o limite do savitch, mas não conheço um limite semelhante para os gráficos ReachFewL.
Derrick Stolee
11
Notícias de COCOON'11: Agora é igual a R e um c h U L . Woohoo! ReumachFeWeu Reumachvocêeu
Hsien-Chih Chang,
9

A última conferência de complexidade mostrou algum progresso nessa questão. Acessibilidade em DAG planares com fontes podem ser resolvidos em O ( log n ) espaçoO(registron)O(registron) .

Aqui também está uma pesquisa recente da Allender: "Problemas de acessibilidade: uma atualização"

Ryan Williams
fonte
Parece que nenhum dos problemas "intermediários" (exceto RL) é conhecido por estar em SC ^ 2.
Shiva Kintali