En la teoría de la complejidad computacional , SL ( Symmetric Logspace o Sym-L ) es la clase de complejidad de problemas log-space reducible a USTCON ( conectividad st no dirigida ), que es el problema de determinar si existe una ruta entre dos vértices en un grafo no dirigido. , descrito de otro modo como el problema de determinar si dos vértices están en el mismo componente conectado . Este problema también se denomina problema de accesibilidad no dirigida . No importa si la reducibilidad de muchos a uno o la reducibilidad de Turingse utiliza. 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 usa 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 a USTCON también han impactado a SL . Por lo tanto, están conectados y discutidos juntos.
En octubre de 2004 Omer Reingold mostró que SL = L .
Origen
SL fue definido por primera vez en 1982 por Harry R. Lewis y Christos Papadimitriou , [1] que buscaban una clase en la que ubicar a USTCON, que hasta ese momento, en el mejor de los casos, podía colocarse solo en NL , a pesar de que aparentemente no requería no determinismo. Definieron la máquina de Turing simétrica , la utilizaron para definir SL, demostraron que USTCON estaba completo para SL y demostraron que
donde L es la clase de problemas más conocida que puede resolver una máquina de Turing determinista ordinaria en el espacio logarítmico, y NL es la clase de problemas que pueden resolver las máquinas de Turing no deterministas en el espacio logarítmico. El resultado de Reingold, discutido más adelante, muestra que, de hecho, cuando se limita al espacio de registro, la máquina de Turing simétrica es equivalente en potencia a la máquina de Turing determinista.
Problemas completos
Por definición, USTCON es completo para SL (todos los problemas en SL se reducen a él, incluido él mismo). Se encontraron muchos problemas completos más interesantes, la mayoría mediante la reducción directa o indirecta de USTCON, y Àlvarez y Greenlaw elaboraron un compendio de ellos. [2] Muchos de los problemas son problemas de teoría de grafos en grafos no dirigidos. Algunos de los problemas completos de SL más simples e importantes que describen incluyen:
- USTCON
- Simulación de máquinas de Turing simétricas: ¿un STM acepta una entrada determinada en un espacio determinado, dado en unario?
- Rutas de vértice-disjuntos: ¿hay k rutas entre dos vértices, compartiendo vértices solo en los puntos finales? (una generalización de USTCON, equivalente a preguntar si una gráfica está conectada con k )
- ¿Un gráfico dado es un gráfico bipartito o, de manera equivalente, tiene un color de gráfico con 2 colores?
- ¿Dos gráficos no dirigidos tienen el mismo número de componentes conectados ?
- ¿Tiene un gráfico un número par de componentes conectados?
- Dado un gráfico, ¿hay un ciclo que contenga una arista determinada?
- ¿Los bosques que se extienden de dos gráficas tienen el mismo número de aristas?
- Dado un gráfico en el que todos sus bordes tienen pesos distintos, ¿hay un borde dado en el bosque que abarca el peso mínimo ?
- Exclusiva o 2- satisfacibilidad : dada una fórmula que requiere que x i xor x j suspenso por un número de pares de variables ( x i , x j ), ¿hay una asignación a las variables que hace verdadera?
Los complementos de todos estos problemas están también en SL, ya que, como veremos, SL está cerrado bajo complemento.
Del hecho de que L = SL , se sigue que muchos más problemas son SL-completos con respecto a las reducciones de espacio logarítmico: todo problema no trivial en L o en SL es SL -completo; además, incluso si las reducciones son de alguna clase más pequeña que L , L -completo es equivalente a SL -completo. En este sentido, esta clase se ha vuelto algo trivial.
Resultados importantes
Hay algoritmos clásicos bien conocidos, tales como la búsqueda en profundidad y la búsqueda en amplitud que resuelven USTCON en el tiempo lineal y el espacio. Su existencia, que se muestra mucho antes de SL se definió, demuestra 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 forma no determinista en cada vértice qué vértice visitar a continuación para descubrir una ruta, si existe.
Sin embargo, el primer resultado no trivial para SL fue el teorema de Savitch , probado en 1970, que proporcionó un algoritmo que resuelve USTCON en un espacio log 2 n . Sin embargo, a diferencia de la búsqueda en profundidad, este algoritmo no es 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 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 en el espacio determinista (uniforme) en el algoritmo de Savitch durante 22 años, Aleliunas et al encontraron un algoritmo de espacio logarítmico probabilístico muy práctico en 1979: simplemente comience en un vértice y realice una caminata aleatoria hasta encontrar el otro. uno (luego aceptar) o hasta | V | Ha pasado 3 veces (luego rechazar). [4] Los rechazos falsos se realizan con una pequeña probabilidad acotada que se reduce exponencialmente cuanto más se continúa la caminata aleatoria. Esto mostró que SL está contenido en RLP , la clase de problemas que se pueden resolver 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 transversal universal, Aleliunas et al. también mostró que SL está contenido en L / poli , una clase de complejidad no uniforme de los problemas que se pueden resolver de forma determinista en el espacio logarítmico con consejos polinomiales .
En 1989, Borodin et al. fortaleció 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 de espacio logarítmico, tiempo polinómico esperado y aleatorización sin errores.
En 1992, Nisan , Szemerédi y Wigderson finalmente encontraron un nuevo algoritmo determinista para resolver USTCON usando solo log 1,5 n de espacio. [6] Esto se mejoró ligeramente, pero no habría ganancias más significativas hasta Reingold.
En 1995, Nisan y Ta-Shma mostraron el sorprendente resultado de que SL se cierra 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 puede resolverse reduciéndolo a un gráfico y preguntando si dos vértices están en el mismo componente, también puede resolverse reduciéndolo a otro gráfico y preguntando si dos vértices están en componentes diferentes . Sin embargo, el artículo de Reingold más tarde 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-uno para mostrar que un problema está en SL ; son equivalentes.
Un avance de octubre de 2004 DOCUMENTO por Omer Reingold mostró que USTCON es, de hecho, en L . [8] Dado que USTCON es SL -completo, esto implica que SL = L , esencialmente eliminando la utilidad de considerar SL como una clase separada. Unas semanas más tarde, el estudiante de posgrado Vladimir Trifonov demostró que USTCON podría resolverse de manera determinista usando el espacio O (log n log log n ), un resultado más débil, usando diferentes técnicas. [9] No ha habido 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 conducen a él) que se preocupan principalmente por los asintóticos; como resultado, el algoritmo que describe en realidad tomaría memoria, y hora. Esto significa que incluso para, el algoritmo requeriría más memoria que la contenida en todas las computadoras del mundo (un kiloexaexaexabyte).
Consecuencias de L = SL
El colapso de L y SL tiene una serie de consecuencias importantes. Lo más obvio es que todos los problemas completos de SL están ahora en L , y pueden emplearse provechosamente en el diseño de algoritmos deterministas de espacio logarítmico y espacio polilogarítmico. En particular, tenemos un nuevo conjunto de herramientas para usar en reducciones de espacio de registro . También se sabe ahora que hay un problema en L si y solo si se puede reducir el espacio logarítmico a USTCON.
Notas al pie
- ^ Lewis, Harry R .; Papadimitriou, Christos H. (1980), "Computación simétrica limitada por el espacio", Actas del Séptimo Coloquio Internacional sobre Autómatas, Lenguajes y Programación , Lecture Notes in Computer Science, 85 , Berlín: Springer, págs. 374–384, doi : 10.1007 / 3-540-10003-2_85 , MR 0589018. Versión de la revista publicada como Lewis, Harry R .; Papadimitriou, Christos H. (1982), "Computación simétrica limitada por el espacio", Ciencias de la computación teóricas , 19 (2): 161-187, doi : 10.1016 / 0304-3975 (82) 90058-5 , MR 0666539
- ^ Álvarez, Carme; Greenlaw, Raymond (2000), "Un compendio de problemas completos para el espacio logarítmico simétrico", Computational Complexity , 9 (2): 123-145, doi : 10.1007 / PL00001603 , MR 1809688.
- ^ Savitch, Walter J. (1970), "Relaciones entre complejidades de cinta deterministas y no deterministas", Journal of Computer and System Sciences , 4 : 177-192, doi : 10.1016 / S0022-0000 (70) 80006-X , hdl : 10338. dmlcz / 120475 , MR 0266702.
- ^ Aleliunas, Romas; Karp, Richard M .; Lipton, Richard J .; Lovász, László ; Rackoff, Charles (1979), "Caminatas al azar, secuencias transversales universales y la complejidad de los problemas del laberinto", Actas del 20º Simposio anual sobre los fundamentos de la informática , Nueva York: IEEE, págs. 218-223, doi : 10.1109 / SFCS .1979.34 , MR 0598110.
- ^ Borodin, Allan ; Cook, Stephen A .; Dymond, Patrick W .; Ruzzo, Walter L .; Tompa, Martin (1989), "Dos aplicaciones del conteo inductivo para problemas de complementación", SIAM Journal on Computing , 18 (3): 559–578, CiteSeerX 10.1.1.394.1662 , doi : 10.1137 / 0218038 , MR 0996836.
- ^ Nisan, Noam ; Szemerédi, Endre ; Wigderson, Avi (1992), "Conectividad no dirigida en el espacio O (log1.5n)", Actas del 33 ° Simposio anual sobre los fundamentos de la informática , págs. 24-29, doi : 10.1109 / SFCS.1992.267822.
- ^ Nisan, Noam ; Ta-Shma, Amnon (1995), "El espacio de registro simétrico está cerrado por complemento", Chicago Journal of Theoretical Computer Science , artículo 1, MR 1345937 , ECCC TR94-003.
- ^ Reingold, Omer (2008), "Conectividad no dirigida en el espacio de registro", Journal of the ACM , 55 (4): 1–24, doi : 10.1145 / 1391289.1391291 , MR 2445014.
- ^ Trifonov, Vladimir (2008), "Un algoritmo espacial O (log n log log n ) para conectividad st no dirigida ", SIAM Journal on Computing , 38 (2): 449–483, doi : 10.1137 / 050642381 , MR 2411031.
Referencias
- C. Papadimitriou . Complejidad computacional . Addison-Wesley, 1994. ISBN 0-201-53082-1 .
- Michael Sipser . Introducción a la Teoría de la Computación . PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X .