In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space. Intuitively, logarithmic space is enough space to hold a constant number of pointers into the input and a logarithmic number of boolean flags.
A generalization of L is NL, which is the class of languages decidable in logarithmic space on a nondeterministic Turing machine. We then trivially have <math>L \subseteq NL<math>. Also, a decider using O(log n) space cannot use more than 2O(log n)=nO(1) time, because this is the total number of possible configurations; thus, <math>L \subseteq P<math>, where P is the class of problems solvable in deterministic polynomial time.
Every problem in L is complete under log-space reductions; since this is useless, weaker reductions are defined which allow identification of stronger complete problems in L, but there is no generally accepted definition of L-complete.
Important open problems include whether L = P, and whether L = NL.
A breakthrough October 2004 paper by Omer Reingold showed that USTCON, the problem of whether there exists a path between two vertices in a given undirected graph, is in L, establishing that L = SL, since USTCON is SL-complete.
One consequence of this is a simple logical characterization of L: it contains precisely those languages expressible in first order logic with an added commutative transitive closure operator (in graph theoretical terms, this turns every connected component into a clique).
- Papadimitriou, Computational Complexity Theory.
- Undirected ST-connectivity in Log-Space. Omer Reingold. Electronic Colloquium on Computational Complexity. No. 94.
|Important complexity classes (more)|
|P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | L | NC | P-C|
|PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH|