SL (complexity)

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.

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. From the fact that L = SL, it follows that many more problems are SL-complete with respect to log-space reductions: every non-trivial problem in L or in SL is SL-complete; moreover, even if the reductions are in some smaller class than L, L-completeness is equivalent to SL-completeness. In this sense this class has become somewhat trivial. 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-SL. Equivalently, 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 make this result redundant. One of the most important corollaries of SL = co-SL is that L SL = 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. This means it does not matter whether we use Turing reducibility or many-one reducibility to show a problem is in SL; they are equivalent. In 2004, a breakthrough paper by Omer Reingold showed that USTCON is in fact in L. This paper used expander graphs to guide the search through the input graph. Since USTCON is SL-complete, Reingold's result implies that SL = L, essentially eliminating the usefulness of consideration of SL as a separate class. A few weeks later, graduate student Vladimir Trifonov showed that USTCON could be solved deterministically using O\text{(log } n \text {log log } n) space—a weaker result—using different techniques. 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 64^{32}\,\log N memory, and O(N^{64^{32}}) time. This means that even for N=2 , the algorithm would require more memory than contained on all computers in the world (a kiloexaexaexabyte). ==Consequences of L = SL == The collapse of L and SL has a number of significant consequences. Most obviously, all SL-complete problems are now in L, 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 in log-space reductions. It is also now known that a problem is in L if and only if it is log-space reducible to USTCON. ==Footnotes== ==References== C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. . Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373741624 under CC BY-SA 4.0; modifications have been made.