Editing SL (complexity) (section)

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 (graph theory)|connected component]]. This problem is also called the '''undirected reachability problem'''. It does not matter whether [[many-one reduction|many-one reducibility]] or [[Turing reduction|Turing reducibility]] is used. Although originally described in terms of [[symmetric Turing machine]]s, 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 (complexity)|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 (complexity)|L]]'''.