st-conectividad
| Temas relevantes sobre |
| Conectividad gráfica |
|---|
En ciencias de la computación , St-conectividad o STCON es un problema de decisión de venta, por vértices s y t en un grafo dirigido , si t es alcanzable desde s .
Formalmente, el problema de decisión viene dado por
- PATH = {⟨ D , s , t ⟩ | D es un gráfico dirigido con un camino desde el vértice s a t } .
Complejidad
Se puede demostrar que el problema 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 está considerando actualmente. El algoritmo termina si se alcanza el nodo objetivo t , o la longitud de la ruta excede hasta ahora 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 por 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 se puede reducir a la conectividad con una reducción del espacio logarítmico . Esto sigue siendo cierto para el caso más fuerte de reducciones de primer orden ( Immerman 1999, pag. 51). La reducción del espacio logarítmico de cualquier idioma en NL a STCON procede de la siguiente manera: Considere la máquina M de Turing del espacio logarítmico no determinista 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 internos, la posición de la cabeza y el contenido de la cinta de trabajo) son polinomialmente muchos. Mapee todos los estados posibles de la máquina de espacio logarítmico determinista a los vértices de un gráfico y coloque un borde entre uyv si se puede alcanzar el estado v 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 al 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 denomina conectividad st no dirigida y Omer Reingold demostró que es L -completo . 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 mostró que SL es la misma clase que L. En gráficas alternas, el problema es P -completo ( Immerman 1999 , p. 54).
Referencias
- Sipser, Michael (2006), Introducción a la teoría de la computación , Tecnología del curso Thompson, ISBN 0-534-95097-3
- Immerman, Neil (1999), Descriptive Complexity , Nueva York: Springer-Verlag, ISBN 0-387-98600-6
- Conectividad gráfica
- Gráficos dirigidos
- Problemas NL-completos
