Algoritmos de espaço de log eficiente

É 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.$L$$P$$O(n^k)$$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(n^k)$$k \leq 10$$k \leq 10$
• 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?$RL$$O(n^3)$$RL$$O(n{\log}^i{n})$

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

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(n^2)$

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.

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(\log n)$

• 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.

$n$$n$

$O(n)$

IIUC, acho que isso satisfaz sua $NC^1$