Incomputational complexity theory,SL (Symmetric Logspace orSym-L) is thecomplexity class of problemslog-space reducible toUSTCON (undirected s-t connectivity), which is the problem of determining whether there exists a path between two vertices in anundirected graph, otherwise described as the problem of determining whether two vertices are in the sameconnected component. This problem is also called theundirected reachability problem. It does not matter whethermany-one reducibility orTuring reducibility is used. Although originally described in terms ofsymmetric Turing machines, that equivalent formulation is very complex, and the reducibility definition is what is used in practice.

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

In October 2004Omer Reingold showed thatSL =L.

SL was first defined in 1982 byHarry R. Lewis andChristos Papadimitriou,^[1] who were looking for a class in which to place USTCON, which until this time could, at best, be placed only inNL, despite seeming not to require nondeterminism. They defined thesymmetric Turing machine, used it to define SL, showed that USTCON was complete for SL, and proved that

${\displaystyle \mathsf{L}\subseteq \mathsf{S}\mathsf{L}\subseteq \mathsf{N}\mathsf{L}}$

whereL is the more well-known class of problems solvable by an ordinarydeterministic Turing machine in logarithmic space, and NL is the class of problems solvable bynondeterministic Turing machines in logarithmic space. The result of Reingold, discussed later, shows that in fact, when limited to log space, the symmetric Turing machine is equivalent in power to the deterministic Turing machine.

By definition, USTCON is complete for SL (all problems in SL reduce to it, including itself). Many more interesting complete problems were found, most by reducing directly or indirectly from USTCON, and a compendium of them was made by Àlvarez and Greenlaw.^[2] Many of the problems aregraph theory problems on undirected graphs. Some of the simplest and most important SL-complete problems they describe include:

• USTCON
• Simulation of symmetric Turing machines: does an STM accept a given input in a certain space, given in unary?
• Vertex-disjoint paths: are therek paths between two vertices, sharing vertices only at the endpoints? (a generalization of USTCON, equivalent to asking whether a graph isk-connected)
• Is a given graph abipartite graph, or equivalently, does it have agraph coloring using 2 colors?
• Do two undirected graphs have the same number ofconnected components?
• Does a graph have an even number of connected components?
• Given a graph, is there a cycle containing a given edge?
• Do thespanning forests of two graphs have the same number of edges?
• Given a graph where all its edges have distinct weights, is a given edge in theminimum weight spanning forest?
• Exclusive or 2-satisfiability: given a formula requiring that${\displaystyle x_i}$ or${\displaystyle x_j}$ hold for a number of pairs of variables${\displaystyle (x_i,x_j)}$, is there an assignment to the variables that makes it true?

Thecomplements of all these problems are in SL as well, since, as we will see, SL is closed under complement.

From the fact thatL =SL, it follows that many more problems are SL-complete with respect to log-space reductions: every non-trivial problem inL or inSL isSL-complete; moreover, even if the reductions are in some smaller class thanL,L-completeness is equivalent toSL-completeness. In this sense this class has become somewhat trivial.

There are well-known classical algorithms such asdepth-first search andbreadth-first search which solve USTCON in linear time and space. Their existence, shown long beforeSL was defined, proves thatSL is contained inP. It's also not difficult to show that USTCON, and soSL, is inNL, since we can just nondeterministically guess at each vertex which vertex to visit next in order to discover a path if one exists.

The first nontrivial result forSL, however, wasSavitch's theorem, proved in 1970, which provided an algorithm that solves USTCON in log²n space. Unlike depth-first search, however, this algorithm is impractical for most applications because of its potentially superpolynomial running time. One consequence of this is that USTCON, and soSL, is inDSPACE(log²n).^[3] (Actually, Savitch's theorem gives the stronger result thatNL is inDSPACE(log²n).)

Although there were no (uniform)deterministic space improvements on Savitch's algorithm for 22 years, a highly practical probabilistic log-space algorithm was found in 1979 by Aleliunas et al.: simply start at one vertex and perform arandom walk until you find the other one (then accept) or until|V|³ time has passed (then reject).^[4] False rejections are made with a small bounded probability that shrinks exponentially the longer the random walk is continued. This showed thatSL is contained inRLP, the class of problems solvable in polynomial time and logarithmic space with probabilistic machines that reject incorrectly less than 1/3 of the time. By replacing the random walk by a universal traversal sequence, Aleliunas et al. also showed thatSL is contained inL/poly, a non-uniform complexity class of the problems solvable deterministically in logarithmic space with polynomialadvice.

In 1989, Borodin et al. strengthened this result by showing that thecomplement of USTCON, determining whether two vertices are in different connected components, is also inRLP.^[5] This placed USTCON, andSL, in co-RLP and in the intersection ofRLP and co-RLP, which isZPLP, the class of problems which have log-space, expected polynomial-time, no-error randomized algorithms.

In 1992,Nisan,Szemerédi, andWigderson finally found a new deterministic algorithm to solve USTCON using only log^1.5n space.^[6] This was improved slightly, but there would be no more significant gains until Reingold.

In 1995, Nisan and Ta-Shma showed the surprising result thatSL is closed under complement, which at the time was believed by many to be false; that is,SL = co-SL.^[7] Equivalently, if a problem can be solved by reducing it to a graph and asking if two vertices are in thesame component, it can also be solved by reducing it to another graph and asking if two vertices are indifferent components. However, Reingold's paper would later make this result redundant.

One of the most important corollaries ofSL = co-SL is thatL^SL =SL; that is, a deterministic, log-space machine with anoracle forSL can solve problems inSL (trivially) but cannot solve any other problems. This means it does not matter whether we use Turing reducibility or many-one reducibility to show a problem is inSL; they are equivalent.

In 2004, a breakthrough paper byOmer Reingold showed that USTCON is in fact inL.^[8] This paper usedexpander graphs to guide the search through the input graph. Since USTCON isSL-complete, Reingold's result implies thatSL =L, essentially eliminating the usefulness of consideration ofSL as a separate class. A few weeks later, graduate student Vladimir Trifonov showed that USTCON could be solved deterministically using${\displaystyle O\text{(log }n\text{log log }n)}$ space—a weaker result—using different techniques.^[9] There has not been substantial effort into turning Reingold's algorithm for USTCON into a practical formulation. It is explicit in his paper (and those leading up to it) that they are primarily concerned with asymptotics; as a result, the algorithm he describes would actually take${\displaystyle {64}^{32}\log N}$ memory, and${\displaystyle O(N^{{64}^{32}})}$ time. This means that even for${\displaystyle N=2}$, the algorithm would require more memory than contained on all computers in the world (a kiloexaexaexabyte).

The collapse ofL andSL has a number of significant consequences. Most obviously, allSL-complete problems are now inL, and can be gainfully employed in the design of deterministic log-space and polylogarithmic-space algorithms. In particular, we have a new set of tools to use inlog-space reductions. It is also now known that a problem is inL if and only if it is log-space reducible to USTCON.

• C. Papadimitriou.Computational Complexity. Addison-Wesley, 1994.ISBN 0-201-53082-1.
• Michael Sipser.Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997ISBN 0-534-94728-X.

• Complexity classes