Editing L (complexity) (section)

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