Class Description

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

Linked From

⊕L: Parity L

Has the same relation to L as ⊕P does to P.

Contains SL [KW93].

Solving a linear system over Z2 is complete for ⊕L [Dam90].

The problem of simulating stabilizer circuits is complete for ⊕L [AG04].

⊕L⊕L = ⊕L [BDH+92], [HRV00].

More about...


coSL: Complement of SL

More about...


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


L/poly: Nonuniform Logarithmic Space

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

Equals PBP [Cob66].

Contains SL [AKL+79].

More about...


ModkL: Mod-k L

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

More about...