Editing Space complexity (section)

==LOGSPACE==
{{main|L (complexity)}}

L or LOGSPACE is the set of problems that can be solved by a deterministic Turing machine using only <math>O(\log n)</math> memory space with regards to input size. Even a single counter that can index the entire <math>n</math>-bit input requires <math>\log n</math> space, so LOGSPACE algorithms can maintain only a constant number of counters or other variables of similar bit complexity.

LOGSPACE and other sub-linear space complexity is useful when processing large data that cannot fit into a computer's [[Random access memory|RAM]]. They are related to [[Streaming algorithm]]s, but only restrict how much memory can be used, while streaming algorithms have further constraints on how the input is fed into the algorithm.
This class also sees use in the field of [[pseudorandomness]] and [[derandomization]], where researchers consider the open problem of whether [[L (complexity)|L]] = [[RL (complexity)|RL]].<ref>{{citation
 | last = Nisan | first = Noam | author-link = Noam Nisan
 | contribution = RL ⊆ SC
 | doi = 10.1145/129712.129772
 | location = Victoria, British Columbia, Canada
 | pages = 619–623
 | title = Proceedings of the 24th ACM Symposium on Theory of computing (STOC '92)
 | year = 1992| isbn = 0-89791-511-9 | s2cid = 11651375 }}.</ref><ref>{{citation
 | last1 = Reingold | first1 = Omer | author1-link = Omer Reingold
 | last2 = Trevisan | first2 = Luca | author2-link = Luca Trevisan
 | last3 = Vadhan | first3 = Salil | author3-link = Salil Vadhan
 | contribution = Pseudorandom walks on regular digraphs and the RL vs. L problem
 | contribution-url = http://people.seas.harvard.edu/~salil/research/regular.pdf
 | doi = 10.1145/1132516.1132583
 | mr = 2277171
 | pages = 457–466
 | publisher = ACM | location = New York
 | title = STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing
 | year = 2006| isbn = 1-59593-134-1 | s2cid = 17360260 }}</ref>

The corresponding nondeterministic space complexity class is [[NL (complexity)|NL]].