En la teoría de la complejidad computacional , el teorema de Immerman-Szelepcsényi establece que las clases de complejidad espacial no determinista están cerradas bajo complementación. Fue probado de forma independiente por Neil Immerman y Róbert Szelepcsényi en 1987, por el que compartieron el Premio Gödel de 1995 . En su forma general, el teorema establece que NSPACE ( s ( n )) = co-NSPACE ( s ( n )) para cualquier función s ( n ) ≥ log n . El resultado se indica de forma equivalente como NL= co-NL; aunque este es el caso especial cuando s ( n ) = log n , implica el teorema general mediante un argumento de relleno estándar . [1] El resultado resolvió el segundo problema de LBA .
En otras palabras, si una máquina no determinista puede resolver un problema, otra máquina con los mismos límites de recursos puede resolver su problema de complemento (con las respuestas sí y no invertidas) en la misma cantidad de espacio asintótica. No se conoce un resultado similar para las clases de complejidad temporal y, de hecho, se conjetura que NP no es igual a co-NP .
El principio utilizado para demostrar el teorema se conoce como conteo inductivo . También se ha utilizado para probar otros teoremas en complejidad computacional, incluido el cierre de LOGCFL bajo complementación y la existencia de algoritmos de espacio de registro aleatorios sin errores para USTCON . [2]
Boceto de prueba
El teorema se puede demostrar mostrando cómo traducir cualquier máquina de Turing no determinista M en otra máquina de Turing no determinista que resuelva el problema de decisión complementario bajo O de las mismas restricciones de espacio, más un número constante de punteros y contadores, que necesita sólo una cantidad logarítmica de espacio.
La idea es simular todas las configuraciones de M y comprobar si se acepta alguna configuración. Esto se puede hacer en NSPACE de la misma magnitud, pero también necesita un número constante de punteros y contadores para realizar un seguimiento de las configuraciones. Si no se acepta ninguna configuración, la máquina de simulación de Turing acepta la entrada; por tanto, acepta si y sólo si M no tiene una ruta de aceptación. Esta idea se elabora a continuación para NSPACE logarítmico ( NL ); la generalización a un NSPACE más grande es sencilla, pero también se puede probar mediante el relleno .
Los estados de M (descritos por la posición de su cabeza en la cinta de entrada y la configuración de la memoria de trabajo del espacio logarítmico) pueden considerarse como los vértices de un grafo dirigido , y las transiciones de M pueden considerarse como aristas. en este gráfico. M acepta una cadena de entrada siempre que exista una ruta en este gráfico desde el vértice s que representa el estado inicial hasta un vértice especial t que representa cualquier estado de aceptación. De esta manera, la existencia de un cálculo no determinista aceptable para M puede verse como una versión del problema de conectividad st , para gráficos implícitos en lugar de gráficos dados explícitamente como un gráfico de entrada representado explícitamente. En este punto de vista gráfico, el objetivo de la prueba es encontrar un algoritmo no determinista logspace que acepta sólo cuando hay qué no existe un camino desde s a t en el mismo gráfico implícita.
Un algoritmo que resuelva este problema de no accesibilidad puede basarse en el principio de contar, para cada número i de 1 an (el orden del gráfico implícito), el número r de vértices alcanzables desde s por caminos de longitud como máximo i . Si, en cualquier etapa del algoritmo, se conoce el valor correcto de r para algún valor de i , entonces es posible probar si un vértice dado v es accesible desde s por caminos de longitud como máximo i + 1 , usando lo siguiente subrutina:
- Si v = s , devuelve verdadero
- Inicializar un contador c a 0
- Para cada vértice u en el gráfico implícito, repita los siguientes pasos:
- Nondeterministically buscar un camino de longitud como máximo i de s de u
- Si se encuentra una ruta hacia u , incremente cy pruebe si existe un borde de u a v
- Si c ≠ r , detenga el algoritmo y rechace la entrada. De lo contrario, devuelva verdadero si se encontró un borde de u a v , y falso en caso contrario.
Cuando se usa dentro de un algoritmo no determinista más grande, los únicos cálculos aceptables del algoritmo pueden ser aquellos en los que la subrutina encuentra rutas a todos los vértices alcanzables y calcula la respuesta correcta, por lo que esta subrutina se puede usar como si fuera determinista. Con él en la mano, el algoritmo para probar la no alcanzabilidad de t a partir de s se puede expresar mediante los siguientes pasos:
- Inicializar i en 0 y r en 1
- Repita los siguientes pasos n - 2 veces:
- // r = # vértices alcanzables dentro de i pasos
- Inicializar un contador d en 0
- Para cada vértice v, pruebe si v es accesible desde s dentro de i + 1 pasos, y si es así, incremente d
- Incrementar i y conjunto r a d
- Pruebe si t es accesible desde s dentro de i + 1 pasos, y rechace la entrada si lo es.
- De lo contrario, si i + 1 es igual a n , acepte la entrada.
El algoritmo solo necesita mantener representaciones de un número constante de contadores y vértices en su memoria, por lo que usa espacio logarítmico. Mediante la aplicación de este algoritmo a la gráfica implícita construido a partir de una máquina no determinista dado M , se obtiene una máquina no determinista para la lengua complementaria a la aceptada por M .
Jerarquía del espacio de registro
Como corolario, en el mismo artículo, Immerman demostró que, utilizando la igualdad de complejidad descriptiva entre NL y FO (Transitive Closure) , la jerarquía logarítmica, es decir, los lenguajes decididos por una máquina de Turing alterna en el espacio logarítmico con un número acotado de alternancia , es de la misma clase que NL.
Ver también
- El teorema de Savitch relaciona las clases espaciales no deterministas con sus contrapartes deterministas
Notas
- ^ La referencia estándar para el relleno en la complejidad del espacio (que precede a este teorema) es Savitch, Walter J. (1970), "Relaciones entre complejidades de cinta deterministas y no deterministas", Journal of Computer and System Sciences , 4 : 177-192, doi : 10.1016 / s0022-0000 (70) 80 006-x , hdl : 10338.dmlcz / 120.475 , MR 0266702. Para obtener un argumento de relleno más sólido que se aplique incluso a las clases de complejidad espacial sublogarítmica, consulte Szepietowski, Andrzej (1994), Máquinas de Turing con espacio sublogarítmico , Lecture Notes in Computer Science, 843 , Springer-Verlag, Berlín, doi : 10.1007 / 3-540-58355-6 , ISBN 3-540-58355-6, MR 1314820.
- ^ Borodin, Allan ; Cook, Stephen A .; Dymond, Patrick W .; Ruzzo, Walter L .; Tompa, Martin (1989), "Dos aplicaciones del conteo inductivo para problemas de complementación", SIAM Journal on Computing , 18 (3): 559–578, CiteSeerX 10.1.1.394.1662 , doi : 10.1137 / 0218038.
Referencias
- Immerman, Neil (1988), "El espacio no determinista se cierra bajo complementación" (PDF) , SIAM Journal on Computing , 17 (5): 935–938, doi : 10.1137 / 0217058 , MR 0961049
- Szelepcsényi, Róbert (1987), "El método de forzar para autómatas no deterministas", Boletín de la EATCS , 33 : 96–100
enlaces externos
- Lance Fortnow , Fundamentos de la complejidad, Lección 19: El teorema de Immerman-Szelepcsenyi . Consultado el 09/09/09.