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.
Has the same relation to L as ⊕P does to P.
Solving a linear system over Z2 is complete for ⊕L [Dam90].
The problem of simulating stabilizer circuits is complete for ⊕L [AG04].
The class of decision problems solvable by a Turing machine restricted to use an amount of memory logarithmic in the size of the input, n. (The input itself is not counted as part of the memory.)
L is contained in P. L contains NC1 [Bor77], and is contained in generalizations including NL, L/poly, SL, RL, ⊕L, and ModkL.
Reingold [Rei04] showed that, remarkably, L = SL. In other words, undirected graph connectivity is solvable in deterministic logarithmic space.
Immerman [Imm83] showed that L is the class FO(dtc) of first-order expressible queries with a deterministic transitive closure.
L queries are exactly the one that can be written in a syntactic restriction of While languages.
Has the same relation to L as P/poly does to P.
Has the same relation to L as ModkP does to P.
For any prime k, ModkL contains SL [KW93].
For any prime k, ModkLModkL = ModkL [HRV00].
For any k>1, contains LogFew [BDH+92].