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 . Also, a decider using O(log *n*) space cannot use more than 2^{O(log n)}=*n*^{O(1)} time, because this is the total number of possible configurations; thus, , 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**.

The related class of function problems is **FL**. **FL** is often used to define logspace reductions.

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).

## References

Last updated: 05-13-2005 07:56:04