L (complexity)
The Television & Movie Wiki: for TV, celebrities, and movies.
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.
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
- {{qif
|test={{{Authorlink|}}}
|then={{wikilink
|1={{{Authorlink}}}
|2={{qif
|test={{{Author|}}}
|then=Christos Papadimitriou
|else={{{Last|}}}{{qif
|test={{{First|}}}
|then=, {{{First}}}
}}
}}
}}
|else={{qif
|test={{{Author|}}}
|then=Christos Papadimitriou
|else={{{Last|}}}{{qif
|test={{{First|}}}
|then=, {{{First}}}
}}
}}
}}{{qif
|test={{{Coauthors|}}}
|then=, {{{Coauthors}}}
}}{{qif
|test={{{Date|}}}
|then= ({{{Date}}})
|else={{qif
|test={{{Year|}}}
|then={{qif
|test={{{Month|}}}
|then= ({{{Month}}} 1993)
|else= (1993)
}}
}}
}}{{qif
|test={{{Author|{{{Last|{{{Year|}}}}}}}}}
|then=.
}}{{qif
|test={{{Chapter|}}}
|then= "{{{Chapter}}}"
}}{{qif
|test={{{Editor|}}}
|then= {{{Editor}}}
}} {{qif
|test={{{URL|}}}
|then=[{{{URL}}} Computational Complexity]
|else=Computational Complexity
}}{{qif
|test={{{Others|}}}
|then=, {{{Others}}}
}}{{qif
|test={{{Edition|}}}
|then=, 1st edition
}}{{qif
|test={{{Pages|}}}
|then=, {{{Pages}}}
}}{{qif
|test={{{Publisher|}}}
|then=, {{qif
|test={{{Location|}}}
|then={{{Location}}}:
}}Addison Wesley
}}{{qif
|test={{{ID|}}}
|then=. ISBN 0201530821
}}. Chapter 16: Logarithmic space, pp.395–408.
- Undirected ST-connectivity in Log-Space. Omer Reingold. Electronic Colloquium on Computational Complexity. No. 94.
- {{qif
|test={{{Authorlink|}}}
|then={{wikilink
|1={{{Authorlink}}}
|2={{qif
|test={{{Author|}}}
|then=Michael Sipser
|else={{{Last|}}}{{qif
|test={{{First|}}}
|then=, {{{First}}}
}}
}}
}}
|else={{qif
|test={{{Author|}}}
|then=Michael Sipser
|else={{{Last|}}}{{qif
|test={{{First|}}}
|then=, {{{First}}}
}}
}}
}}{{qif
|test={{{Coauthors|}}}
|then=, {{{Coauthors}}}
}}{{qif
|test={{{Date|}}}
|then= ({{{Date}}})
|else={{qif
|test={{{Year|}}}
|then={{qif
|test={{{Month|}}}
|then= ({{{Month}}} 1997)
|else= (1997)
}}
}}
}}{{qif
|test={{{Author|{{{Last|{{{Year|}}}}}}}}}
|then=.
}}{{qif
|test={{{Chapter|}}}
|then= "{{{Chapter}}}"
}}{{qif
|test={{{Editor|}}}
|then= {{{Editor}}}
}} {{qif
|test={{{URL|}}}
|then=[{{{URL}}} Introduction to the Theory of Computation]
|else=Introduction to the Theory of Computation
}}{{qif
|test={{{Others|}}}
|then=, {{{Others}}}
}}{{qif
|test={{{Edition|}}}
|then=, {{{Edition}}}
}}{{qif
|test={{{Pages|}}}
|then=, {{{Pages}}}
}}{{qif
|test={{{Publisher|}}}
|then=, {{qif
|test={{{Location|}}}
|then={{{Location}}}:
}}PWS Publishing
}}{{qif
|test={{{ID|}}}
|then=. ISBN 0-534-94728-X
}}. Section 8.4: The Classes L and NL, pp.294–296.
- {{qif
|test={{{Authorlink|}}}
|then={{wikilink
|1={{{Authorlink}}}
|2={{qif
|test={{{Author|}}}
|then=Michael R. Garey and David S. Johnson
|else={{{Last|}}}{{qif
|test={{{First|}}}
|then=, {{{First}}}
}}
}}
}}
|else={{qif
|test={{{Author|}}}
|then=Michael R. Garey and David S. Johnson
|else={{{Last|}}}{{qif
|test={{{First|}}}
|then=, {{{First}}}
}}
}}
}}{{qif
|test={{{Coauthors|}}}
|then=, {{{Coauthors}}}
}}{{qif
|test={{{Date|}}}
|then= ({{{Date}}})
|else={{qif
|test={{{Year|}}}
|then={{qif
|test={{{Month|}}}
|then= ({{{Month}}} 1979)
|else= (1979)
}}
}}
}}{{qif
|test={{{Author|{{{Last|{{{Year|}}}}}}}}}
|then=.
}}{{qif
|test={{{Chapter|}}}
|then= "{{{Chapter}}}"
}}{{qif
|test={{{Editor|}}}
|then= {{{Editor}}}
}} {{qif
|test={{{URL|}}}
|then=[{{{URL}}} Computers and Intractability: A Guide to the Theory of NP-Completeness]
|else=Computers and Intractability: A Guide to the Theory of NP-Completeness
}}{{qif
|test={{{Others|}}}
|then=, {{{Others}}}
}}{{qif
|test={{{Edition|}}}
|then=, {{{Edition}}}
}}{{qif
|test={{{Pages|}}}
|then=, {{{Pages}}}
}}{{qif
|test={{{Publisher|}}}
|then=, {{qif
|test={{{Location|}}}
|then={{{Location}}}:
}}W.H. Freeman
}}{{qif
|test={{{ID|}}}
|then=. ISBN 0716710455
}}. 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 | EXPSPACE | PR | RE | Co-RE | RE-C | Co-RE-C | R | BQP | BPP | RP | ZPP | PCP | IP | PH |
