Editing L (complexity) (section)

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