Algoritmos de espaço de log eficiente

17

É fácil ver que qualquer problema decidível no espaço de registro determinístico ( ) é executado no máximo no tempo polinomial ( P ). Muitos algoritmos de espaço de log conhecidos (por exemplo: conectividade st não direcionada, isomorfismo de gráfico plano) são executados em O ( n k ), onde k é incrivelmente grande.LPO(nk)k

  • Estou procurando exemplos de problemas naturais que são conhecidos por serem solucionáveis ​​simultaneamente no espaço de registro determinístico e no tempo que k 10 . Não há nada de especial em 10. Olhando para os algoritmos de espaço de log atualmente conhecidos, acho que k 10 é interessante o suficiente.O(nk)k10k10
  • Aleliunas et al. mostraram que não dirigida r-conectividade é em (logspace randomizado). O tempo de execução de seu algoritmo é O ( n 3 ) . Existem problemas naturais que podem ser resolvidos simultaneamente em R L e tempo linear (OR) perto de tempo linear ou seja, O ( n log i n ) tempo?ReuO(n3)ReuO(nregistroEun)

Edit: Para tornar as coisas mais interessantes, vejamos os problemas que são pelo menos -hard.NC1 1

Shiva Kintali
fonte
Existe alguma análise de tempo para a versão do espaço de log do teorema de Courcelle? eccc.uni-trier.de/report/2010/062
Hsien-Chih Chang #

Respostas:

10

Eu acho que a acessibilidade DAG Planar de coletor único de fonte única (SSPD) possui algoritmo de espaço de log com um tempo de execução modesto ( ?). Não tenho tanta certeza sobre o algoritmo SMPD (Planar Dach Reachability) de fonte única.O(n2)

Ref: Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Problemas de acessibilidade em gráficos de planar e de grade. Teoria Comput. Syst. 45 (4): 675-723 (2009)

Além disso, um novo algoritmo de espaço de log para teste de planaridade e incorporação é executado em tempo modestamente polinomial (acessibilidade indireta do módulo, é claro)

Ref: Samir Datta, Gautam Prakriya: Planarity Testing Revisited CRRR abs / 1101.2637: (2011)

Finalmente, aqui está um problema simples de brinquedo que possui um espaço no log com um tempo de execução modesto (acessibilidade não direcionada do módulo) viz. Isomorfismo Outplanplanar.

SamiD
fonte
11
O algoritmo SSPD é depois que a incorporação planar é encontrada e usa o fato de existirem caminhos de tempo linear e espaço de log que podem ser percorridos "mais à esquerda" e "mais à direita" de qualquer vértice ao coletor ou a fonte para qualquer vértice (chame esses caminhos "externos"). Para encontrar um caminho de u para v , verifique se os vértices sobre os caminhos exteriores de u para a pia estão ao longo dos caminhos exteriores da fonte para v.O(n2)vocêv
Derrick Stolee
9

Essa resposta é mais um problema de brinquedo do que um problema de pesquisa real.

Meu exemplo típico de um algoritmo de espaço de log para dar a amigos programadores é o seguinte quebra-cabeça:

n

O(registron)

  • Avance o primeiro ponteiro da lista em uma etapa.
  • Avance o segundo ponteiro na lista em duas etapas.
  • Se um dos ponteiros encontrar o fim, retorne false.
  • Se os nós apontarem para o mesmo nó, retorne true.
  • Caso contrário, itere novamente.

nn

Derrick Stolee
fonte
3
NC1 1
3

O(n)

IIUC, acho que isso satisfaz sua NC1 1

Neel Krishnaswami
fonte
2
Como você está alterando o gráfico, este não é um algoritmo de espaço de log, em que a fita de entrada deve ser somente leitura. Este é um algoritmo interessante por si só.
Derrick Stolee