En informática , la conectividad st o STCON es un problema de decisión que pregunta, para los vértices syt en un gráfico dirigido , si t es alcanzable desde s .
Formalmente, el problema de decisión está dado por
En una computadora secuencial, la conectividad st se puede resolver fácilmente en tiempo lineal mediante una búsqueda en profundidad o en amplitud . El interés en este problema de complejidad computacional se refiere a su complejidad con respecto a formas más limitadas de computación. Por ejemplo, la clase de complejidad de problemas que puede resolver una máquina de Turing no determinista utilizando sólo una cantidad logarítmica de memoria se llama NL . Se puede demostrar que el problema de conectividad st está en NL, ya que una máquina de Turing no determinista puede adivinar el siguiente nodo de la ruta, mientras que la única información que debe almacenarse es la longitud total de la ruta y qué nodo se encuentra actualmente. bajo consideración. El algoritmo termina si se alcanza el nodo objetivo t o si la longitud de la ruta excede n , el número de nodos en el gráfico.
El complemento de st-conectividad , conocido como st-no-conectividad , también está en la clase NL, ya que NL = coNL según el teorema de Immerman-Szelepcsényi .
En particular, el problema de la conectividad st es en realidad NL completo , es decir, cada problema de la clase NL es reducible a conectividad bajo una reducción del 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 del espacio logarítmico de cualquier lenguaje en NL a STCON procede de la siguiente manera: Considere la máquina de Turing M de espacio logarítmico no determinista que acepta un lenguaje en NL. Dado que solo hay un 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 polinómicamente muchos. Asigne todos los estados posibles de la máquina determinista de espacio logarítmico a los vértices de un gráfico y coloque un borde entre u y v si el estado v se puede alcanzar 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 una ruta 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 O (log 2 n ).
El mismo problema para los gráficos no dirigidos se llama conectividad st no dirigida y Omer Reingold demostró que está en L. Esta investigación le valió el premio Grace Murray Hopper en 2005 . Anteriormente se sabía 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 gráficas alternas, el problema es P -completo (Immerman 1999, p. 54).