Editing SL (complexity) (section)

== Origin ==

SL was first defined in 1982 by [[Harry R. Lewis]] and [[Christos Papadimitriou]],<ref>{{citation
 | last1 = Lewis | first1 = Harry R. | author1-link = Harry R. Lewis
 | last2 = Papadimitriou | first2 = Christos H. | author2-link = Christos Papadimitriou
 | contribution = Symmetric space-bounded computation
 | doi = 10.1007/3-540-10003-2_85
 | location = Berlin
 | mr = 589018
 | pages = 374–384
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Proceedings of the Seventh International Colloquium on Automata, Languages and Programming
 | volume = 85
 | year = 1980}}. Journal version published as {{citation
 | last1 = Lewis | first1 = Harry R. | author1-link = Harry R. Lewis
 | last2 = Papadimitriou | first2 = Christos H. | author2-link = Christos Papadimitriou
 | doi = 10.1016/0304-3975(82)90058-5
 | issue = 2
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 666539
 | pages = 161–187
 | title = Symmetric space-bounded computation
 | volume = 19
 | year = 1982| doi-access = free
 }}</ref> who were looking for a class in which to place USTCON, which until this time could, at best, be placed only in [[NL (complexity)|NL]], despite seeming not to require nondeterminism. They defined the [[symmetric Turing machine]], used it to define SL, showed that USTCON was complete for SL, and proved that
: <math>\mathsf{L} \subseteq \mathsf{SL} \subseteq \mathsf{NL}</math>
where [[L (complexity)|L]] is the more well-known class of problems solvable by an ordinary [[deterministic Turing machine]] in logarithmic space, and NL is the class of problems solvable by [[nondeterministic Turing machines]] in logarithmic space. The result of Reingold, discussed later, shows that in fact, when limited to log space, the symmetric Turing machine is equivalent in power to the deterministic Turing machine.