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(logn) space cannot use more than 2O(logn) = nO(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).
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.
References
- Christos Papadimitriou (1993). Computational Complexity, 1st edition, Addison Wesley. 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.
- Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 8.4: The Classes L and NL, pp.294–296.
- Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. Section 7.5: Logarithmic Space, pp.177–181.
| Important complexity classes (more) |
|---|
| P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
