Class Description

RL: Randomized Logarithmic-Space

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.

Contained in SC [Nis92].

[RTV05] give strong evidence that RL = L.

Linked From

L: Logarithmic Space

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.

More about...


RHL: Randomized Halting Logarithmic-Space

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.

More about...


RSPACE(f(n)): Randomized f(n)-Space

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)).

More about...


SC: Steve's Class

(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 PpolyL, 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.

More about...