Class Description

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

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

LogFew: Logspace-Bounded Few

The class of decision problems solvable by an NL machine such that

  1. The number of accepting paths on input x is f(x), and
  2. The answer is 'yes' if and only if R(x,f(x))=1, where R is some predicate computable in L.

Defined in [BDH+92], where it was also shown that LogFew is contained in ModkL for all k>1.

More about...

ModZkL: Restricted ModkL

The class of decision problems solvable by a nondeterministic logspace Turing machine, such that

  1. If the answer is "yes," then the number of accepting paths is not congruent to 0 mod k.
  2. If the answer is "no," then there are no accepting paths.

Defined in [BDH+92], where it was also shown that ModZkL contains LogFewNL for all k>1.

Contained in ModkL and in NL.

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

More about...

SPL: Stoic PL

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.

Contained in C=L and ModkL.

Equals the set of problems low for GapL.

More about...