conectividad st

En informática , la conectividad st o STCON es un problema de decisión que pregunta, para vértices s y t en un grafo dirigido , si t es alcanzable desde s .

Formalmente, el problema de decisión viene dado por

CAMINO = { ⟨ D , s , t ⟩   | D es un grafo dirigido con un camino desde el vértice s hasta t } .

En una computadora secuencial, la conectividad st se puede resolver fácilmente en tiempo lineal mediante búsqueda en profundidad o búsqueda en amplitud . El interés en este problema en la complejidad computacional radica en su complejidad con respecto a formas de computación más limitadas. Por ejemplo, la clase de complejidad de problemas que puede resolver una máquina de Turing no determinista utilizando solo una cantidad logarítmica de memoria se denomina NL . Se puede demostrar que el problema de conectividad st pertenece a NL, ya que una máquina de Turing no determinista puede adivinar el siguiente nodo del camino, mientras que la única información que debe almacenarse es la longitud total del camino y el nodo que se está considerando actualmente. El algoritmo termina si se alcanza el nodo objetivo t , o si la longitud del camino hasta el momento excede n , el número de nodos en el grafo.

El complemento de la st-conectividad , conocida como st-no-conectividad , también está en la clase NL, ya que NL  =  coNL por el teorema de Immerman-Szelepcsényi .

En particular, el problema de la st-conectividad es en realidad NL-completo , es decir, todo problema en la clase NL es reducible a conectividad bajo una reducción de espacio logarítmico . Esto sigue siendo cierto para el caso más fuerte de reducciones de primer orden ( Immerman 1999 , p. 51) . La reducción de espacio logarítmico de cualquier lenguaje en NL a STCON procede de la siguiente manera: Consideremos la máquina de Turing no determinista de espacio logarítmico M que acepta un lenguaje en NL. Dado que solo hay espacio logarítmico en la cinta de trabajo, todos los estados posibles de la máquina de Turing (donde un estado es el estado de la máquina de estados finitos interna, la posición del cabezal y el contenido de la cinta de trabajo) son polinomialmente muchos. Mapeamos todos los estados posibles de la máquina determinista de espacio logarítmico a vértices de un grafo, y colocamos una arista entre u y v si el estado v puede alcanzarse desde u dentro de un paso de la máquina no determinista. Ahora bien, el problema de si la máquina acepta es el mismo que el problema de si existe un camino desde el estado inicial hasta el estado de aceptación. 

El teorema de Savitch garantiza que el algoritmo se puede simular en un espacio determinista de O (log ² n ). 

El mismo problema para grafos no dirigidos se denomina conectividad st no dirigida y Omer Reingold demostró que pertenece a L. Esta investigación le valió el premio Grace Murray Hopper de 2005. Se sabía previamente que la conectividad st no dirigida era completa para la clase SL , por lo que el trabajo de Reingold demostró que SL es la misma clase que L. En grafos alternantes, el problema es P -completo ( Immerman 1999 , p. 54) .  

• Sipser, Michael (2006), Introducción a la teoría de la computación , Thompson Course Technology, ISBN 0-534-95097-3
• Immerman, Neil (1999), Complejidad descriptiva , Nueva York: Springer-Verlag, ISBN 0-387-98600-6