Algoritmos de espacio de registro eficientes

Es fácil ver que cualquier problema que sea decidible en el espacio de registro determinista ( ) se ejecuta en la mayoría de los casos de polinomios ( P ). Muchos algoritmos de espacio de registro conocidos (por ejemplo: conectividad st no dirigida, isomorfismo de gráfico plano) se ejecutan en O ( n k ) donde k es increíblemente grande.$L$$P$$O(n^k)$$k$

• Estoy buscando ejemplos de problemas naturales que se sabe que se pueden resolver simultáneamente en el espacio de registro determinista y el tiempo donde k ≤ 10 . No hay nada especial en 10. Mirando los algoritmos de espacio de registro conocidos actualmente, creo que k ≤ 10 es lo suficientemente interesante.$O(n^k)$$k \leq 10$$k \leq 10$
• Aleliunas y col. mostró que la conectividad st no dirigida está en (espacio de registro aleatorio). El tiempo de ejecución de su algoritmo es O ( n 3 ) . ¿Existen problemas naturales que se puedan resolver simultáneamente en R L y en el tiempo lineal (o) cerca del tiempo lineal, es decir, el tiempo O ( n log i n ) ?$RL$$O(n^3)$$RL$$O(n{\log}^i{n})$

Editar: para hacer las cosas más interesantes echemos un vistazo a los problemas que son al menos -duros.$NC^1$

Supongo que la accesibilidad DAG plana (DPS) de un solo sumidero tiene un algoritmo de espacio de registro con un tiempo de ejecución modesto ( ?). No estoy tan seguro sobre el algoritmo de alcance de DAG plano de sumidero múltiple de fuente única (SMPD).$O(n^2)$

Ref: Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: problemas de accesibilidad de gráficos planos y de cuadrícula. Teoría de la Computación. Syst. 45 (4): 675-723 (2009)

Además, un nuevo algoritmo de espacio de registro para pruebas de planaridad e incrustaciones se ejecuta en un tiempo polinomial moderado (alcance de módulo no dirigido, por supuesto)

Ref: Samir Datta, Gautam Prakriya: Prueba de planaridad Revisado CoRR abs / 1101.2637: (2011)

Finalmente, aquí hay un problema de juguete simple que tiene un espacio de registro algo con un tiempo de ejecución modesto (módulo de accesibilidad no dirigida) a saber. Isomorfismo del plano externo.

Esta respuesta es más un problema de juguete que un problema de investigación real.

Mi ejemplo típico de un algoritmo de espacio de registro para dar a los amigos programadores es el siguiente rompecabezas:

Dada una lista vinculada de tamaño desconocido ( ) y utilizando un número constante de variables de puntero, determine si la lista vinculada alguna vez se repite.$n$

La solución es un algoritmo de espacio de registro, que utiliza dos punteros de tamaño para nodos de lista vinculados. Comience ambos al comienzo de la lista vinculada y realice el siguiente procedimiento iterativo:$O(\log n)$

• Avance el primer puntero de la lista en un paso.
• Avance el segundo puntero en la lista por dos pasos.
• Si cualquiera de los punteros encuentra el final, devuelve falso.
• Si los nodos apuntan al mismo nodo, devuelve verdadero.
• De lo contrario, repita nuevamente.

$n$$n$

$O(n)$

$NC^1$