Has the same relation to L as RP does to P. The randomized machine must halt with probability 1 on any input. It must also run in polynomial time (since otherwise we would just getNL).
Contains RHL.
[RTV05] give strong evidence that RL = L.
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 RP does to P. The randomized machine must halt for every input and every setting of the random tape.
Contains undirected reachability (is there a path from vertex u to vertex v in an undirected graph?) [AKL+79].
Contained in RL.
Same as RL, but for O(f(n))-space instead of logarithmic-space. (Just as an RL machine must run in polynomial time, so an RSPACE(f(n)) machine must run in 2O(f(n)) time.)
Contained in NSPACE(f(n)) and BPSPACE(f(n)).
(Named in honor of Stephen Cook.)
The class of decision problems solvable by a Turing machine that simultaneously uses polynomial time and polylogarithmic space.
Note that SC might be smaller than P ∩ polyL, since for the latter, it suffices to have two separate algorithms: one polynomial-time and the other polylogarithmic-space.
Deterministic context-free languages (DCFLs) can be recognized in SC [Coo79].
SC contains RL and BPL [Nis92].
SC equals DTISP(poly,polylog) by definition.