View source for L (complexity)

{{short description|Complexity class (logarithmic space)}}
{{redirect-distinguish|Logspace|Logscale}}
[[File:The relations between various L-related complexity classes.png|thumb|The relations between various '''L'''-related complexity classes. Produced by tracing out the various class containment statements from [[Complexity Zoo]].]]
In [[computational complexity theory]], '''L''' (also known as '''LSPACE''', '''LOGSPACE''' or '''DLOGSPACE''') is the [[complexity class]] containing [[decision problem]]s that can be solved by a [[deterministic Turing machine]] using a [[logarithm]]ic amount of writable [[Memory space (computational resource)|memory space]].<ref name="sip295">{{harvp|Sipser|1997|loc=Definition 8.12|p=295}}</ref><ref name="gj-177">{{harvp|Garey|Johnson|1979|p=177}}</ref> Formally, the Turing machine has two tapes, one of which encodes the input and can only be read,<ref>On a read/write input tape, a linear amount of memory could be obtained by packing of symbols (as in the proof of the [[linear speedup theorem]]), thus evading the logspace contraint.</ref> whereas the other tape has logarithmic size but can be written as well as read. Logarithmic space is sufficient to hold a constant number of [[pointer (computer programming)|pointer]]s into the input<ref name="sip295" /> and a logarithmic number of Boolean flags, and many basic logspace algorithms use the memory in this way.

==Complete problems and logical characterization==
Every non-trivial problem in '''L''' is [[Complete (complexity)|complete]] under [[log-space reduction]]s,<ref>See {{harvp|Garey|Johnson|1979|loc=Theorem 7.13 (claim 2)|p=179}}</ref> so weaker reductions are required to identify meaningful notions of '''L'''-completeness, the most common being [[FO (complexity)|first-order]] [[First-order reduction|reductions]].

A 2004 result by [[Omer Reingold]] shows that [[USTCON]], the problem of whether there exists a path between two vertices in a given [[undirected graph]], is in '''L''', showing that '''L''' = '''[[SL (complexity)|SL]]''', since USTCON is '''SL'''-complete.<ref>{{cite conference
 | last = Reingold | first = Omer
 | title = Undirected ST-connectivity in log-space
 | doi = 10.1145/1060590.1060647
 | id = {{ECCC|2004|04|094}}
 | mr = 2181639
 | pages = 376–385
 | publisher = ACM, New York
 | conference = [[Symposium on Theory of Computing|STOC'05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing]]
 | url = http://www.wisdom.weizmann.ac.il/~reingold/publications/sl.ps
 | year = 2005}}</ref>

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 theory|graph theoretical]] terms, this turns every [[connected component (graph theory)|connected component]] into a [[clique (graph theory)|clique]]). This result has application to database [[query language]]s: ''[[data complexity]]'' of a query is defined as the complexity of answering a fixed query considering the data size as the variable input. For this measure, queries against [[relational database]]s with complete information (having no notion of [[Null (SQL)|null]]s) as expressed for instance in [[relational algebra]] are in '''L'''.

==Related complexity classes==

'''L''' is a subclass of '''[[NL (complexity)|NL]]''', which is the class of languages decidable in [[logarithm]]ic space on a [[nondeterministic Turing machine]]. A problem in '''NL''' may be transformed into a problem of [[reachability]] in a [[directed graph]] representing states and state transitions of the nondeterministic machine, and the logarithmic space bound implies that this graph has a polynomial number of vertices and edges, from which it follows that '''NL''' is contained in  the complexity class '''[[P (complexity)|P]]''' of problems solvable in deterministic polynomial time.<ref>{{harvtxt|Sipser|1997}}, Corollary&nbsp;8.21, p.&nbsp;299.</ref> Thus '''L'''&nbsp;⊆&nbsp;'''NL'''&nbsp;⊆&nbsp;'''P'''. The inclusion of '''L''' into '''P''' can also be proved more directly: a decider using ''O''(log&nbsp;''n'') space cannot use more than 2<sup>''O''(log&nbsp;''n'')</sup>&nbsp;=&nbsp;''n''<sup>''O''(1)</sup> time, because this is the total number of possible configurations.

'''L''' further relates to the class '''[[NC (complexity)|NC]]''' in the following way:
'''NC'''<sup>1</sup>&nbsp;⊆&nbsp;'''L'''&nbsp;⊆&nbsp;'''NL'''&nbsp;⊆&nbsp;'''NC'''<sup>2</sup>.
In words, given a parallel computer ''C'' with a polynomial number ''O''(''n''<sup>''k''</sup>) of processors for some constant ''k'', any problem that can be solved on ''C'' in ''O''(log&nbsp;''n'') time is in '''L''', and any problem in '''L''' can be solved in ''O''(log<sup>2</sup>&nbsp;''n'') time on ''C''.

{{Unsolved|computer science|{{tmath|1= \mathsf{L} \overset{?}{=} \mathsf{P} }}}}

Important [[List of unsolved problems in computer science|open problems]] include whether '''L'''&nbsp;=&nbsp;'''P''',<ref name="gj-177"/> and whether '''L'''&nbsp;=&nbsp;'''NL'''.<ref>{{harvp|Sipser|1997|p=297}}; {{harvp|Garey|Johnson|1979|p=180}}</ref>  It is not even known whether '''L'''&nbsp;=&nbsp;'''[[NP (complexity)|NP]]'''.<ref>{{Cite web|url=https://cs.stackexchange.com/questions/103073/is-it-possible-that-l-np|title = Complexity theory - is it possible that L&nbsp;=&nbsp;NP}}</ref>

The related class of [[function problem]]s is '''[[FL (complexity)|FL]]'''.  '''FL''' is often used to define [[logspace reduction]]s.

== Random versions ==
Just as how '''P''' has several random versions: '''[[BPP (complexity)|BPP]]''', '''[[ZPP (complexity)|ZPP]]''', '''[[PP (complexity)|PP]]''', and '''[[RP (complexity)|RP]]''', there are several random versions of '''L'''.

'''Bounded-error Probability L''' ('''BPL''') is defined like '''BPP''', as the complexity class of problems solvable with a logspace Turing machine such that:

* Other than the usual tapes of a logspace Turing machine, the machine also takes a tape filled with random bits.
* The randomness is read-only and one-way. That is, the read-head on the random tape can only move in one direction. To reference a previous random bit, the machine must store it in the work tape.
* The Turing machine has to halt for every input and every random tape.
* If the answer is 'yes' then the machine accepts with probability at least 2/3. If the answer is 'no' then the machine rejects with probability at least 2/3.

It is contained in '''NC'''<sup>''2''</sup>, which is contained in '''P'''.<ref>{{Cite journal |last1=Borodin |first1=A. |last2=Cook |first2=S. |last3=Pippenger |first3=N. |date=1983-07-01 |title=Parallel computation for well-endowed rings and space-bounded probabilistic machines |url=https://www.sciencedirect.com/science/article/pii/S0019995883800606 |journal=Information and Control |volume=58 |issue=1 |pages=113–136 |doi=10.1016/S0019-9958(83)80060-6 |issn=0019-9958}}</ref>

'''BP•L''' is defined the same as '''BPL''', except that the machine is allowed to read the random tape both forwards and backwards. It contains '''BPL'''. It is also exactly equal to the class of languages that are nearly logspace: a language is nearly logspace if, [[Oracle machine|relative]] to almost every oracle, the language is in '''L'''.<ref name=":0" />

'''ZP•L''' is defined like '''BP•L''', except that the machine may output "unknown", and must never make an error (i.e. accept when the answer is 'no', and vice versa). The relation of '''ZP•L''' to '''BP•L''', is the same as the relation of [[ZPP (complexity)|'''ZPP''']] to [[BPP (complexity)|'''BPP''']]. It contains '''BPL''' and is contained by '''BP•L'''.<ref name=":0">{{Cite journal |last=Nisan |first=Noam |date=1993-01-04 |title=On read once vs. multiple access to randomness in logspace |url=https://dx.doi.org/10.1016/0304-3975%2893%2990258-U |journal=Theoretical Computer Science |volume=107 |issue=1 |pages=135–144 |doi=10.1016/0304-3975(93)90258-U |issn=0304-3975}}</ref>

'''Randomized L''' ('''RL''') is defined like '''BPL''':

* Other than the usual tapes of a logspace Turing machine, the machine also takes a read-only one-way tape filled with random bits.
* The Turing machine has to halt for every input and every random tape.
* If the answer is 'yes,' accept with probability at least 1/2.
* If the answer is 'no,' always reject.

Also, it must always run in polynomial time (since otherwise we would just get '''[[NL (complexity)|NL]]'''). It is strongly suspected that '''RL''' = '''L'''.<ref>{{Cite book |last1=Reingold |first1=Omer |last2=Trevisan |first2=Luca |last3=Vadhan |first3=Salil |chapter=Pseudorandom walks on regular digraphs and the RL vs. L problem |date=2006-05-21 |title=Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing |chapter-url=https://dl.acm.org/doi/10.1145/1132516.1132583 |series=STOC '06 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=457–466 |doi=10.1145/1132516.1132583 |isbn=978-1-59593-134-4}}</ref>

Both '''BPL''' and '''RL''' are contained in [[Steve's Class]].<ref>{{Cite journal |last=Nisan |first=Noam |date=1994-03-01 |title=RL ⊆ SC |url=https://link.springer.com/article/10.1007/BF01205052 |journal=Computational Complexity |language=en |volume=4 |issue=1 |pages=1–11 |doi=10.1007/BF01205052 |issn=1420-8954|url-access=subscription }}</ref>

'''Probabilistic L''' ('''PL''') has the same relation to '''L''' that '''[[PP (complexity)|PP]]''' has to '''P''': 

* If the answer is 'yes,' accept with probability at least 1/2.
* If the answer is 'no,' reject with probability at least 1/2.
It contains '''BPL''', and is contained by '''NC'''<sup>''2''</sup>.<ref>{{Cite journal |last=Cook |first=Stephen A. |date=1985-01-01 |title=A taxonomy of problems with fast parallel algorithms |url=https://www.sciencedirect.com/science/article/pii/S0019995885800413 |journal=Information and Control |series=International Conference on Foundations of Computation Theory |volume=64 |issue=1 |pages=2–22 |doi=10.1016/S0019-9958(85)80041-3 |issn=0019-9958|doi-access=free }}</ref>

==Additional properties==
'''L''' is [[low (complexity)|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.

==Other uses==
The main idea of logspace is that one can store a polynomial-magnitude number in logspace and use it to remember pointers to a position of the input.

The logspace class is therefore useful to model computation where the input is too big to fit in the [[Random-access memory|RAM]] of a computer. Long [[DNA]] sequences and databases are good examples of problems where only a constant part of the input will be in RAM at a given time and where we have pointers to compute the next part of the input to inspect, thus using only logarithmic memory.

==See also==
*[[L/poly]], a nonuniform variant of L that captures the complexity of polynomial-size [[branching program]]s

==Notes==
{{reflist}}

==References==
* {{cite book | zbl=1193.68112 | last1=Arora | first1=Sanjeev | last2=Barak | first2=Boaz | title=Computational complexity. A modern approach | publisher=[[Cambridge University Press]] | year=2009 | isbn=978-0-521-42426-4}}
* {{cite book|first=Christos|last=Papadimitriou| year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1| at = Chapter 16: Logarithmic space, pp.&nbsp;395–408}}
* {{cite book | first = Michael | last = Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X| at = Section 8.4: The Classes L and NL, pp.&nbsp;294–296 | url-access = registration | url = https://archive.org/details/introductiontoth00sips }}
* {{cite book | last1=Garey | first1=M.R. | author1-link=Michael Garey | last2=Johnson | first2=D.S. | author2-link=David S. Johnson | year=1979 | title=[[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher=W.H. Freeman | isbn=0-7167-1045-5|mr=0519066|oclc=247570676| at=[https://archive.org/details/computersintract0000gare/page/ Section 7.5: Logarithmic Space, pp.&nbsp;177–181] }}
* {{cite journal | last1=Cook | first1=Stephen A. | author1-link=Stephen Arthur Cook | last2=McKenzie | first2=Pierre | title = Problems Complete for Deterministic Logarithmic Space | journal = Journal of Algorithms| volume=8 | number=3 | pages=385–394 |year=1987|issn=0196-6774|doi=10.1016/0196-6774(87)90018-6 | url = http://www.cs.utoronto.ca/~sacook/homepage/cook_mckenzie.pdf}}

{{ComplexityClasses}}

[[Category:Complexity classes]]