L (clase de complejidad)

En teoría de la complejidad computacional, la clase de complejidad L (LSPACE o 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

Véase también

Other Languages
Esperanto: L (komplikeco)
français: L (complexité)
한국어: L (복잡도)
português: LSPACE
русский: Класс L
српски / srpski: L (сложеност)
Tiếng Việt: L (độ phức tạp)