En la teoría de la complejidad computacional , SL ( Simetric Logspace o Sym-L ) es la clase de complejidad de problemas log-espacio reducibles a USTCON ( undirected st connectivity ), que es el problema de determinar si existe un camino entre dos vértices en un grafo no dirigido , de otra manera descrito como el problema de determinar si dos vértices están en el mismo componente conexo . Este problema también se llama problema de alcanzabilidad no dirigida . No importa si se utiliza la reducibilidad de muchos-uno o la reducibilidad de Turing . Aunque originalmente se describió en términos de máquinas de Turing simétricas , esa formulación equivalente es muy compleja, y la definición de reducibilidad es la que se utiliza en la práctica.
USTCON es un caso especial de STCON ( accesibilidad dirigida ), el problema de determinar si existe una ruta dirigida entre dos vértices en un grafo dirigido , que es completo para NL . Debido a que USTCON es SL -completo, la mayoría de los avances que impactan en USTCON también han impactado SL . Por lo tanto, están conectados y se analizan juntos.
En octubre de 2004, Omer Reingold demostró que SL = L .
SL fue definida por primera vez en 1982 por Harry R. Lewis y Christos Papadimitriou [1] , quienes buscaban una clase en la que colocar USTCON, que hasta ese momento, en el mejor de los casos, solo podía ubicarse en NL , a pesar de que aparentemente no requería no determinismo. Definieron la máquina de Turing simétrica , la usaron para definir SL, demostraron que USTCON era completa para SL y probaron que
donde L es la clase más conocida de problemas que se pueden resolver con una máquina de Turing determinista ordinaria en el espacio logarítmico, y NL es la clase de problemas que se pueden resolver con máquinas de Turing no deterministas en el espacio logarítmico. El resultado de Reingold, que se analiza más adelante, muestra que, de hecho, cuando se limita al espacio logarítmico, la máquina de Turing simétrica es equivalente en potencia a la máquina de Turing determinista.
Por definición, USTCON es completo para SL (todos los problemas en SL se reducen a él, incluido él mismo). Se encontraron muchos más problemas completos interesantes, la mayoría mediante reducción directa o indirecta a partir de USTCON, y Àlvarez y Greenlaw realizaron un compendio de ellos. [2] Muchos de los problemas son problemas de teoría de grafos sobre grafos no dirigidos. Algunos de los problemas SL-completos más simples e importantes que describen incluyen:
Los complementos de todos estos problemas también están en SL, ya que, como veremos, SL es cerrado bajo complemento.
Del hecho de que L = SL , se sigue que muchos más problemas son SL-completos con respecto a las reducciones en el espacio logarítmico: todo problema no trivial en L o en SL es SL -completo; además, incluso si las reducciones están en una clase más pequeña que L , la L -completitud es equivalente a la SL -completitud. En este sentido, esta clase se ha vuelto algo trivial.
Existen algoritmos clásicos bien conocidos, como la búsqueda en profundidad y la búsqueda en amplitud, que resuelven USTCON en tiempo y espacio lineales. Su existencia, demostrada mucho antes de que se definiera SL , prueba que SL está contenido en P . Tampoco es difícil demostrar que USTCON, y por lo tanto SL , está en NL , ya que podemos adivinar de manera no determinista en cada vértice qué vértice visitar a continuación para descubrir un camino si existe.
Sin embargo, el primer resultado no trivial para SL fue el teorema de Savitch , demostrado en 1970, que proporcionó un algoritmo que resuelve USTCON en el espacio log 2 n . Sin embargo, a diferencia de la búsqueda en profundidad, este algoritmo es poco práctico para la mayoría de las aplicaciones debido a su tiempo de ejecución potencialmente superpolinomial. Una consecuencia de esto es que USTCON, y por lo tanto SL , está en DSPACE (log 2 n ) . [3] (En realidad, el teorema de Savitch da el resultado más fuerte de que NL está en DSPACE (log 2 n ) .)
Aunque no hubo mejoras espaciales deterministas (uniformes) en el algoritmo de Savitch durante 22 años, Aleliunas et al. encontraron en 1979 un algoritmo probabilístico de espacio logarítmico altamente práctico: simplemente comience en un vértice y realice un paseo aleatorio hasta encontrar el otro (luego acepte) o hasta que haya pasado | V | 3 tiempo (luego rechace). [4] Los rechazos falsos se realizan con una pequeña probabilidad acotada que se reduce exponencialmente cuanto más se continúa el paseo aleatorio. Esto mostró que SL está contenido en RLP , la clase de problemas resolubles en tiempo polinomial y espacio logarítmico con máquinas probabilísticas que rechazan incorrectamente menos de 1/3 del tiempo. Al reemplazar el paseo aleatorio por una secuencia de recorrido universal, Aleliunas et al. también demostraron que SL está contenido en L/poly , una clase de complejidad no uniforme de los problemas resolubles determinísticamente en el espacio logarítmico con asesoramiento polinomial .
En 1989, Borodin et al. reforzaron este resultado al mostrar que el complemento de USTCON, que determina si dos vértices están en diferentes componentes conectados, también está en RLP . [5] Esto colocó a USTCON y SL en co- RLP y en la intersección de RLP y co- RLP , que es ZPLP, la clase de problemas que tienen algoritmos aleatorizados de espacio de registro, tiempo polinomial esperado y sin error.
En 1992, Nisan , Szemerédi y Wigderson finalmente encontraron un nuevo algoritmo determinista para resolver USTCON usando solo un espacio de log 1,5 n . [6] Esto se mejoró ligeramente, pero no habría ganancias más significativas hasta Reingold.
En 1995, Nisan y Ta-Shma demostraron el sorprendente resultado de que SL es cerrado bajo complemento, lo que en ese momento muchos creían que era falso; es decir, SL = co- SL . [7] De manera equivalente, si un problema se puede resolver reduciéndolo a un gráfico y preguntando si dos vértices están en el mismo componente, también se puede resolver reduciéndolo a otro gráfico y preguntando si dos vértices están en componentes diferentes . Sin embargo, el artículo de Reingold haría que este resultado fuera redundante.
Uno de los corolarios más importantes de SL = co- SL es que L SL = SL ; es decir, una máquina determinista, de espacio logarítmico, con un oráculo para SL puede resolver problemas en SL (trivialmente) pero no puede resolver ningún otro problema. Esto significa que no importa si usamos la reducibilidad de Turing o la reducibilidad de muchos a uno para mostrar que un problema está en SL ; son equivalentes.
En 2004, un artículo innovador de Omer Reingold mostró que USTCON está de hecho en L . [8] Este artículo utilizó gráficos expansores para guiar la búsqueda a través del gráfico de entrada. Dado que USTCON es SL -completo, el resultado de Reingold implica que SL = L , eliminando esencialmente la utilidad de considerar SL como una clase separada. Unas semanas más tarde, el estudiante de posgrado Vladimir Trifonov demostró que USTCON podía resolverse de manera determinista utilizando el espacio (un resultado más débil) utilizando técnicas diferentes. [9] No se ha hecho un esfuerzo sustancial para convertir el algoritmo de Reingold para USTCON en una formulación práctica. Es explícito en su artículo (y en los que lo antecedieron) que se ocupan principalmente de las asintóticas; como resultado, el algoritmo que describe en realidad ocuparía memoria y tiempo. Esto significa que incluso para , el algoritmo requeriría más memoria que la contenida en todas las computadoras del mundo (un kiloexaexaexabyte).
El colapso de L y SL tiene varias consecuencias significativas. La más obvia es que todos los problemas SL -completos están ahora en L y pueden emplearse de forma provechosa en el diseño de algoritmos deterministas en el espacio logarítmico y en el espacio polilogarítmico. En particular, tenemos un nuevo conjunto de herramientas para usar en reducciones en el espacio logarítmico . Ahora también se sabe que un problema está en L si y solo si es reducible en el espacio logarítmico a USTCON.
