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].
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.
The class of decision problems solvable by an NL machine such that
Defined in [BDH+92], where it was also shown that LogFew is contained in ModkL for all k>1.
The class of decision problems solvable by a nondeterministic logspace Turing machine, such that
Defined in [BDH+92], where it was also shown that ModZkL contains LogFewNL for all k>1.
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 PL as SPP does to PP.
Contains the maximum matching and perfect matching problems under a pseudorandom assumption [ARZ99].
Contains UL.
Equals the set of problems low for GapL.