What is "sl"

__NOTOC__ SL may refer to:

• Serjeant-at-law, an obsolete legal position in the United Kingdom
• Sensei's Library, an internet website and wiki dedicated to the ancient game of Go
• Sensu lato, a term used in taxonomy to mean "in the wider sense" of a definition
• Standard length, a commonly used measurement for fish: the length from tip of the snout to the posterior end of the last vertebra

In computational complexity theory, SL (Symmetric Logspace or Sym-L) is the complexity class of problems log-space reducible to USTCON (undirected s-t connectivity), which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same connected component. This problem is also called the undirected reachability problem. 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.

USTCON is a special case of STCON (directed reachability), the problem of determining whether a directed path between two vertices in a directed graph exists, which is complete for NL. Because USTCON is SL-complete, most advances that impact USTCON have also impacted SL. Thus they are connected, and discussed together.

In October 2004 Omer Reingold showed that SL = L.