Límites inferiores apretados en el teorema de Savitch

En primer lugar, me disculpo de antemano por cualquier estupidez. De ninguna manera soy un experto en teoría de la complejidad (¡lejos de eso! Soy un estudiante universitario que toma mi primera clase en teoría de la complejidad). Aquí está mi pregunta. Ahora el teorema de Savitch establece que Ahora tengo curiosidad por saber si este límite inferior era ajustado, es decir, algo no se puede lograr.

NSPACE (f (n)) \subseteq DSPACE ({(f (n))}^{2})

$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right)$

NSPACE (f (n)) \subseteq DSPACE ({(f (n))}^{1.9})

$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^{1.9}\right)$

Parece que debería haber un argumento combinatorio directo aquí: cada nodo en el gráfico de configuración para una máquina de Turing determinista tiene solo un borde saliente, mientras que cada nodo en el gráfico de configuración de una máquina de Turing no determinista puede tener más de un borde saliente Lo que está haciendo el algoritmo de Savitch es convertir gráficos de configuración con cualquier número de borde saliente en gráficos de configuración con bordes salientes. $<2$

Dado que el gráfico de configuración define un TM único (no estoy seguro de esto), el tamaño combinatorio de este último es casi seguro mayor que el primero. Esta "diferencia" es quizás un factor de , quizás menos, no lo sé. Por supuesto, hay muchos pequeños problemas técnicos que resolver, como la forma en que debe asegurarse de que no haya bucles, etc., pero mi pregunta es si esta es una forma razonable de comenzar a probar algo como esto. $n^2$

cc.complexity-theory space-bounded gabgoh
fuente

Respuestas:

Esta es una pregunta abierta bien conocida. Verás en la teoría de la complejidad muchas preguntas abiertas para las que te preguntarás cómo es que nadie logró resolverlas. Parte de la razón es que necesitamos nuevas personas como tú para ayudarnos a resolverlos :)

Para obtener el último resultado en esta área, que muestra que el algoritmo de Savitch es óptimo en algunos modelos restringidos, consulte el documento FOCS de Aaron Potechin .

Específicamente, parte de la agradable observación de que debido a que el gráfico de configuración de un TM determinista tiene solo un borde saliente (después de arreglar la entrada), uno puede pensar en él como un gráfico no dirigido, por lo que la pregunta se convierte en algo como lo siguiente: dado un gráfico dirigido de vértices con dos vértices especiales , si lo asignamos a un gráfico de vértice no dirigido (también con vértices especiales ) de modo que la existencia de cada borde en depende de un borde en y hay un camino de a en si y sólo si hay un camino entre $G$ $n$ $s,t$ $N$ $G'$ $s',t'$ $G'$ $G$ $s$ $t$ $G$ $s'$ y en , cuánto más grande tiene que ser de . $t'$ $G'$ $N$ $n$

Para mostrar que el algoritmo de Savitch es óptimo, uno debe demostrar que tiene que ser al menos . Para mostrar , es suficiente mostrar el límite más débil que para cada constante . Estoy bastante seguro de que incluso no se conoce, aunque quizás algo como se conozca por algunas razones no tan interesantes. $N$ $2^{\Omega(\log^2 n)} = n^{\Omega(\log n)}$ $L\neq NL$ $N > n^c$ $c$ $N > n^{10}$ $N \geq n^2$

Boaz Barak
fuente

Creo que no sabemos si esto es apretado. De lo contrario, sabríamos que . $L \neq NL$

Karolina Sołtys
fuente

buen punto, gracias :) En la segunda pregunta: ¿ves algún defecto obvio en el enfoque combinatorio para mostrar algo así?

gabgoh

El teorema de Savitch es un algoritmo específico para simular un algoritmo de espacio f (n) no determinista mediante el uso de dividir y conquistar con una profundidad O (f (n)) (dando f (n) ^ 2). Probar límites inferiores implica mostrar que TODOS los algoritmos que usan menos espacio fallan en algunas entradas. Esta es la razón por la que L = NL es difícil (y P = NP es difícil).

Derrick Stolee

No sabemos si es estricto en el sentido de que no sabemos que 2 es lo mejor que se puede hacer, pero eso no significa que no sepamos

N S p a c e (f (n)) \subseteq D S p a c e ((f (n))^{1.9})

$NSpace(f(n)) \subseteq DSpace((f(n))^{1.9})$

Kaveh

Bueno, nosotros no. Cualquier mejora (incluso para

específica , como

) sería un gran avance.

f

$f$

\log n

$\log n$

Derrick Stolee

@Derrick Stolee: Te estás perdiendo el punto de mi comentario. Solo conocer una respuesta positiva implicaría que

, el argumento de Karolina no proporciona ninguna evidencia de la dificultad de conocer una respuesta negativa, es decir, conocer

no parece que ayuda con

L \neq N L

$L \neq NL$

N S p a c e (f (n)) \subseteq D S p a c e ((f (n))^{1.9})

$NSpace(f(n)) \subseteq DSpace((f(n))^{1.9})$

L

$L$

N L

$NL$

Kaveh