¿Cómo demostrar que USTCONN requiere espacio logarítmico?

USTCONN es el problema que requiere decidir si hay una ruta desde el vértice de origen hasta el vértice de destino en un gráfico , donde todos estos se dan como parte de la entrada.$s$$t$$G$

Omer Reingold demostró que USTCONN está en L (doi: 10.1145 / 1391289.1391291 ). La prueba construye un expansor de grado constante por medio del producto en zig-zag. Un expansor de grado constante tiene diámetro logarítmico y luego se pueden verificar todas las rutas posibles utilizando un número constante de marcadores de tamaño logarítmico.

El resultado de Reingold da un límite superior logarítmico en la complejidad espacial de USTCONN, resolviendo su complejidad espacial "hasta un factor constante" según el documento. Tengo curiosidad sobre el límite inferior correspondiente, que no se menciona en ningún otro lugar en el documento.

¿Cómo se prueba que se requiere espacio logarítmico para decidir USTCONN en el peor de los casos?

Editar: corrija la representación de entrada para que sea la matriz de adyacencia del gráfico directo simétrico simple vértice subyacente , con las filas enumeradas consecutivamente para formar una cadena de bits.$N \times N$$N$$N^2$

Lewis y Papadimitriou mostraron (doi: 10.1016 / 0304-3975 (82) 90058-5 ) que USTCONN es SL-complete, lo que con el resultado de Reingold implica que SL = L. Savitch mostró (doi: 10.1016 / S0022-0000 (70) 80006-X ) que . Además para cualquier función computable de Stearns, Hartmanis y Lewis (doi: 10.1109 / FOCS .1965.11 ), por lo que se necesita al menos espacio para USTCONN. Finalmente, se sabe que las clases habituales están por debajo de L (como$\text{NSPACE}(n) \subseteq \text{DSPACE}(n^2)$$\text{DSPACE}(f(n)) = \text{DSPACE}(1)$Ω ( log log n ) NC $f(n) = o(\log\log n)$$\Omega(\log\log n)$$\text{NC}^1$) se definen en términos de circuitos y obviamente no son comparables a ninguna clase definida en términos de un espacio limitado.

Hasta donde puedo ver, esto deja abierta la posibilidad (ciertamente improbable) de que haya un algoritmo determinista aún mejor que solo use el espacio pero , para algún , o incluso un algoritmo no determinista para USTCONN que usa el espacio .Ω ( log log n ) δ < 1 O ( ( log n ) 1 / 2$O((\log n)^\delta)$$\Omega(\log \log n)$$\delta < 1$$o((\log n)^{1/2})$

Según el teorema de la jerarquía espacial , siempre que f (n) sea ​​construible en el espacio. Esto podría sugerir que USTCONN no puede estar en \ text {DSPACE} (o (\ log n)) . Sin embargo, USTCONN estar completo para L bajo reducciones de espacio de registro no parece implicar esto. Parece posible que USTCONN tenga suficiente estructura para codificar cualquier problema en L mediante una reducción de espacio de registro, sin embargo, USTCONN solo requiere espacio sublogarítmico.$\text{DSPACE}(o(f(n)) \subsetneq \text{DSPACE}(f(n))$$f(n)$$\text{DSPACE}(o(\log n))$

Mientras exista algún lenguaje en L que requiera espacio logarítmico, entonces mostrar que USTCONN está completo para L bajo un estrictamente "más débil" que la reducción de espacio de registro produciría el límite inferior deseado.

¿Está USTCONN completo para L bajo una reducción que requiere espacio ?$o(\log n)$

Immerman mostró (doi: 10.1137 / 0216051 ) que una versión de accesibilidad dirigida en la que la ruta deseada (pero no el gráfico en sí) es determinista, está completa para L bajo reducciones de primer orden, que son computables por circuitos AC . Esto podría entonces adaptarse para mostrar que USTCONN está completo para L bajo las reducciones de FO. Sin embargo, aunque AC está estrictamente contenido en L, AC es nuevamente una clase de circuito y no conozco ninguna forma de realizar reducciones de FO en el espacio sublogarítmico.$^0$$^0$$^0$

Edición 2015-07-14: Es un tema filosófico interesante si el uso del espacio de una TM debe incluir el tamaño de un índice en la entrada (permitiendo así el acceso aleatorio a la entrada, pero necesita un bit adicional si la entrada duplica su tamaño ), o si el espacio utilizado por una TM es el número de cuadrados de la cinta de trabajo visitados durante un cálculo (lo que supone que el cabezal de la cinta de entrada es fijo y no cambia cuando la cinta de entrada duplica su tamaño). La antigua definición de estilo RAM proporciona inmediatamente un límite inferior de espacio de registro para cualquiercomputación y modela las computadoras actuales que realizan un seguimiento de la posición actual en un archivo como un desplazamiento desde el inicio del archivo. La última definición clásica supone una cinta similar al papel con un cabezal de lectura fijo que no sabe nada sobre la cinta que no sea el símbolo de entrada actual, que posiblemente sea lo que Turing pretendía en su artículo de 1937.

Argumentos heurísticos como el comentario de Thomas, de que ni siquiera es posible indexar la entrada con bits de espacio, parecen asumir una definición moderna de estilo RAM. Stearns / Hartmanis / Lewis utilizan la definición de estilo TM, al igual que la mayoría de los trabajos clásicos en computación limitada por el espacio.$o(\log n)$

Uno puede probar un límite inferior de espacio de registro para USTCONN representado como una matriz de adyacencia al observar que el lenguaje unario de cuadrados perfectos requiere espacio de registro para reconocer (ver Rūsiņš Freivalds, Modelos de computación, Hipótesis de Riemann y Matemáticas clásicas , SOFSEM 1998, LNCS 1521, 89 –106. Doi: 10.1007 / 3-540-49477-4_6 ( preimpresión)). Entonces, el mismo límite inferior se aplica a USTCONN con la representación de matriz de adyacencia. Tal vez esto sea demasiado engañoso: por lo general, hacer cumplir la promesa en un problema de promesa debe ser fácil en comparación con el problema real, pero aquí hacer cumplir la promesa de que la entrada es un gráfico ya da el límite inferior. Por lo tanto, sería bueno ver un argumento para un límite inferior del espacio de registro para el problema de promesa donde se garantiza que la entrada sea del idioma .$\{\{0,1\}^{N \times N} \mid N=1,2,\dots\}$

El artículo Cuantificadores de conteo, relaciones de sucesor y espacio logarítmico , de Kousha Etessami, demuestra que el problema (que esencialmente verifica si un vértice precede a un vértice en un grafo de grado , que promete ser un camino ) es -duro bajo proyecciones libres de cuantificador.$\mathbf{ORD}$$s$$t$$G$$\mathsf{L}$

Se puede ver que el problema se reduce al problema , por -reducciones: Dada una instancia of simplemente elimine el borde de y genera los otros bordes como bordes no dirigidos la pregunta es si están conectados en el gráfico resultante. (Nota: la reducción probablemente se puede hacer aún más fina).$\mathbf{ORD}$$\mathbf{USTCONN}$$\mathsf{FO}$$\langle G,s,t\rangle$$\mathbf{ORD}$$t$$u \rightarrow v$$\{u,v\}$$\mathbf{USTCONN}$$s,t$