Class Description

L/poly: Nonuniform Logarithmic Space

Has the same relation to L as P/poly does to P.

Equals PBP [Cob66].

Contains SL [AKL+79].

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 NC¹ [Bor77], and is contained in generalizations including NL, L/poly, SL, RL, ⊕L, and Mod_kL.

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

PBP: Polynomial-Size Branching Program

Same as k-PBP but with no width restriction.

Equals L/poly [Cob66].

Contains P-OBDD, BP_d(P).

More about...

SL: Symmetric Logarithmic-Space

The class of problems solvable by a nondeterministic Turing machine in logarithmic space, such that

1. If the answer is 'yes,' one or more computation paths accept.
2. If the answer is 'no,' all paths reject.
3. If the machine can make a nondeterministic transition from configuration A to configuration B, then it can also transition from B to A. (This is what 'symmetric' means.)

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 Mod_kL for every prime k.

SL is also contained in DSPACE(log^3/2n) [NSW92], and indeed in DSPACE(log^4/3n) [ATW+00].

[NT95] showed that SL equals coSL, and furthermore that SL^SL = 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.

More about...