Class Description

coSL: Complement of SL

Linked From

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