SL (complexity)
In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON, which is the problem of whether two vertices in an undirected graph have a path between them, otherwise described as the problem of determining whether two vertices are in the same connected component. It does not matter whether many-one reducibility or Turing reducibility is used. Although originally described in terms of symmetric Turing machines, that equivalent formulation is very complex, and the reducibility definition is what is used in practice.
Complete problems
Using the above definition, USTCON is trivially complete for SL (all problems in SL reduce to it).
Important results
The first main result for SL was Savitch's theorem, the proof of which provides an algorithm which solves USTCON in (log n)2 space, implying that all problems in SL can be solved in this much space. It used this algorithm to prove a general result about space in nondeterministic machines by representing the branching of those machines by an undirected graph and then determining if an accepting state is reachable from the start state.1
For 22 years, this remained the best algorithm for USTCON. Then, in 1992, Nisan, Szemerédi, and Wigderson found an algorithm to solve it using only (log n)1.5 space 2. This was improved slightly, but there would be no more significant gains until Reingold.
In 1995, Nisan and Ta-Shma showed the surprising result that SL is closed under complement, which at the time was believed by many to be false; that is, SL = co-SL2. Put another way, if a problem can be solved by reducing it to a graph and asking if two vertices are in the same component, it can also be solved by reducing it to another graph and asking if two vertices are in different components. However, Reingold's paper would later show this result to be trivial.
One of the most important corollaries of SL = co-SL is that LSL = SL; that is, a deterministic, log-space machine with an oracle for SL can solve problems in SL (trivially) but cannot solve any other problems. In practice, this means it doesn't matter whether we use Turing reducibility or many-one reducibility to show a problem is in SL; they are equivalent.
A breakthrough October 2004 paper by Omer Reingold showed that USTCON is in fact in L, the more well-known space of problems solvable by an ordinary deterministic Turing machine in logarithmic space. Since USTCON is SL-complete, this implies that SL = L, essentially eliminating the usefulness of consideration of SL as a separate class.