Espacio logarítmico
De Wikipedia, la enciclopedia libre
En teoría de la complejidad computacional, la clase de complejidad L (espacio logarítmico determinista) es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, por una máquina de Turing determinista tal que la solución si existe es única. La clase L está contenida en NL y está contenida estrictamente en PSPACE. Como NL también está contenida estrictamente en PSPACE, se concluye que en la relación
P es diferente de NP o bien NP es diferente de PSPACE, pero no se sabe cual de las dos inclusiones es propia.
Véase también: Espacio logarítmico, simétrico (SL)
| 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 |
