SL (clase de complejidad)

En teoría de la complejidad computacional, la clase de complejidad SL (espacio logarítmico simétrico, del inglés Symmetric Logspace o Sym-L) es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, tal que:

1. Si la respuesta es positiva, existe uno o más cómputos de la máquina que aceptan.
2. Si la respuesta es negativa, todos los cómputos de la máquina rechazan la entrada.
3. Si la máquina puede hacer una transición no determinista entre una configuración A y una configuración B, también puede hacer una transición de B hacia A (condición de simetría).

En 2004 se demostró que esta clase de complejidad es equivalente a L. En otras palabras, la condición de simetría en la máquina de Turing no determinista la hace equivalente a una máquina de Turing determinista.

Referencias

• H. R. Lewis y C. H. Papadimitriou. Symmetric space-bounded computation, Theoretical Computer Science 19:161-187, 1982.
• O. Reingold. Undirected st-connectivity in log-space, no publicado, 2004

• Datos: Q6138961