L (COMPLEXITY)

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 $mathrm\{L\}\; subseteq\; mathrm\{NL\}$. 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, $mathrm\{L\}\; subseteq\; mathrm\{P\}$, 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).
'L' is low for itself, because it can simulate log-space oracle queries (roughly speaking, "function calls which use log space") in log space, reusing the same space for each query.

Contents

References

References

★ Computational Complexity, Christos Papadimitriou, , , Addison Wesley, 1993, ISBN 0-201-53082-1 Chapter 16: Logarithmic space, pp.395–408.

★ Undirected ST-connectivity in Log-Space. Omer Reingold. Electronic Colloquium on Computational Complexity. No. 94.

★ Introduction to the Theory of Computation, Michael Sipser, , , PWS Publishing, 1997, ISBN 0-534-94728-X Section 8.4: The Classes L and NL, pp.294–296.

★ , Michael R. Garey and David S. Johnson, , , W.H. Freeman, 1979, ISBN 0-7167-1045-5 Section 7.5: Logarithmic Space, pp.177–181.