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 demostrado independientemente por Neil Immerman y Róbert Szelepcsényi en 1987, por lo 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 expresa de manera 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 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 complementario (con las respuestas sí y no invertidas) en la misma cantidad asintótica de espacio. No se conoce ningún 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 demostrar otros teoremas en complejidad computacional, incluido el cierre de LOGCFL bajo complementación y la existencia de algoritmos de espacio logarítmico aleatorios sin errores para USTCON . [2]
Demostramos aquí que NL = co-NL. El teorema se obtiene a partir de este caso especial mediante un argumento de relleno .
El problema de st-conectividad pregunta, dado un dígrafo G y dos vértices s y t , si existe un camino dirigido desde s hasta t en G . Este problema es NL-completo, por lo tanto su complemento st-no-conectividad es co-NL-completo. Basta con mostrar que la st-no-conectividad está en NL. Esto demuestra co-NL ⊆ NL, y por complementación, NL ⊆ co-NL.
Fijamos un dígrafo G , un vértice fuente s y un vértice destino t . Denotamos por R k el conjunto de vértices que son alcanzables desde s en como máximo k pasos. Nótese que si t es alcanzable desde s , es alcanzable en como máximo n-1 pasos, donde n es el número de vértices, por lo tanto estamos reducidos a probar si t ∉ R n-1 .
Observamos que R 0 = { s }, y R k +1 es el conjunto de vértices v que están en R k o el objetivo de una arista w → v donde w está en R k . Esto da inmediatamente un algoritmo para decidir t ∈ R n , calculando sucesivamente R 1 , …, R n . Sin embargo, este algoritmo utiliza demasiado espacio para resolver el problema en NL, ya que almacenar un conjunto R k requiere un bit por vértice.
La idea crucial de la prueba es que en lugar de calcular R k +1 a partir de R k , es posible calcular el tamaño de R k +1 a partir del tamaño de R k , con la ayuda del no determinismo. Iteramos sobre los vértices e incrementamos un contador para cada vértice que se encuentre que pertenece a R k +1 . El problema es cómo determinar si v ∈ R k +1 para un vértice dado v , cuando solo tenemos disponible el tamaño de R k .
Para ello, iteramos sobre los vértices w y, para cada w , suponemos de manera no determinista si w ∈ R k . Si suponemos w ∈ R k y v = w o hay una arista w → v , entonces determinamos que v pertenece a R k +1 . Si esto falla para todos los vértices w , entonces v no pertenece a R k +1 .
Por lo tanto, el cálculo que determina si v pertenece a R k +1 se divide en ramas para las diferentes suposiciones de qué vértices pertenecen a R k . Se necesita un mecanismo para hacer que todas estas ramas aborten (rechacen inmediatamente), excepto aquella en la que todas las suposiciones fueron correctas. Para esto, cuando hemos hecho una "suposición afirmativa" de que w ∈ R k , verificamos esta suposición, buscando de manera no determinista un camino de s a w de longitud como máximo k . Si esta verificación falla, abortamos la rama actual. Si tiene éxito, incrementamos un contador de "suposiciones afirmativas". Por otro lado, no verificamos las "suposiciones no" de que w ∉ R k (esto requeriría resolver la no conectividad st , que es precisamente el problema que estamos resolviendo en primer lugar). Sin embargo, al final del bucle sobre w , comprobamos que el contador de “intentos afirmativos” coincide con el tamaño de R k , que ya conocemos. Si no coincide, abortamos. De lo contrario, todos los “intentos afirmativos” fueron correctos y hubo exactamente el número correcto de ellos, por lo que todos los “intentos no” también fueron correctos.
Esto concluye el cálculo del tamaño de R k +1 a partir del tamaño de R k . Iterativamente, calculamos los tamaños de R 1 , R 2 , …, R n-2 . Finalmente, verificamos si t ∈ R n-1 , lo cual es posible a partir del tamaño de R n -2 mediante el subalgoritmo que se utiliza dentro del cálculo del tamaño de R k +1 .
El siguiente pseudocódigo resume el algoritmo:
función verificar_alcanzable(G, s, w, k) // Verifica que w ∈ R k . Si este no es el caso, cancela // la rama de cálculo actual, rechazando la entrada. si s = w entonces devuelve c ← s repetir k veces // Se cancela si no hay una arista desde c, de lo contrario // las ramas no deterministas adivinan una arista c → d en G c ← d si c = w entonces regresamos // No adivinamos una ruta. rechazarfunction is_reachable(G, s, v, k, S) // Suponiendo que R k tiene tamaño S, determina si v ∈ R k+1 . reachable ← false yes_guesses ← 0 // contador de sí-conjeturas w ∈ R k para cada vértice w de G do // Adivina si w ∈ R k adivina un booleano b si b entonces verificar_alcanzable(G, s, w, k) sí_conjeturas += 1 si v = w o hay una arista w → v en G entonces alcanzable ← verdadero si yes_guesses ≠ S entonces rechazar // número incorrecto de sí-conjeturas devuelve alcanzablefunción st_no_conectividad(G, s, t) n ← recuento_de_vértices(G) // Tamaño de R k , inicialmente 1 porque R 0 = {s} S ← 1 para k de 0 a n-3 hacer S' ← 0 // tamaño de R k+1 para cada vértice v de G hacer si es_alcanzable(G, s, v, k, S) entonces S'+= 1 S ← S' devuelve no es_alcanzable(G, s, t, n-2, S)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 alternada en un espacio logarítmico con un número acotado de alternancias, es la misma clase que NL.