SL (complejidad)
De Wikipedia, la enciclopedia libre
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:
- Si la respuesta es positiva, existe uno o más cómputos de la máquina que aceptan.
- Si la respuesta es negativa, todos los cómputos de la máquina rechazan la entrada.
- 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.
[editar] 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
| clases de complejidad más importantes |
| L | NL | P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C |
| PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH |
