The class of problems solvable by a nondeterministic Turing machine in logarithmic space, such that
Defined in [LP82].
The undirected s-t connectivity problem (USTCON: is there a path from vertex s to vertex t in a given undirected graph?) is complete for SL, under L-reductions.
SL contains L, and is contained in NL.
It follows from [AKL+79] that SL is contained in L/poly.
[KW93] showed that SL is contained in ⊕L, as well as ModkL for every prime k.
SL is also contained in DSPACE(log3/2n) [NSW92], and indeed in DSPACE(log4/3n) [ATW+00].
[NT95] showed that SL equals coSL, and furthermore that SLSL = SL (that is, the symmetric logspace hierarchy collapses).
Reingold ultimately showed that SL = L [Rei04], even relative to an oracle. This subsumes many of the earlier results.