Editing SL (complexity) (section)

== Important results ==
There are well-known classical algorithms such as [[depth-first search]] and [[breadth-first search]] which solve USTCON in linear time and space. Their existence, shown long before '''SL''' was defined, proves that '''SL''' is contained in '''P'''. It's also not difficult to show that USTCON, and so '''SL''', is in '''NL''', 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 for '''SL''', however, was [[Savitch's theorem]], proved in 1970, which provided an algorithm that solves USTCON in log<sup>2</sup> ''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 so '''SL''', is in {{math|{{sans-serif|DSPACE}}(log<sup>2</sup>''n'')}}.<ref>{{citation
 | last = Savitch | first = Walter J. | author-link = Walter Savitch
 | journal = Journal of Computer and System Sciences
 | mr = 0266702
 | pages = 177–192
 | title = Relationships between nondeterministic and deterministic tape complexities
 | volume = 4
 | year = 1970
 | doi=10.1016/S0022-0000(70)80006-X| hdl = 10338.dmlcz/120475
 | hdl-access = free
 }}.</ref> (Actually, Savitch's theorem gives the stronger result that '''NL''' is in {{math|{{sans-serif|DSPACE}}(log<sup>2</sup>''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 a [[random walk]] until you find the other one (then accept) or until {{math|{{abs|{{var|V}}}}<sup>3</sup>}} time has passed (then reject).<ref>{{citation
 | last1 = Aleliunas | first1 = Romas
 | last2 = Karp | first2 = Richard M. | author2-link = Richard M. Karp
 | last3 = Lipton | first3 = Richard J. | author3-link = Richard J. Lipton
 | last4 = Lovász | first4 = László | author4-link = László Lovász
 | last5 = Rackoff | first5 = Charles | author5-link = Charles Rackoff
 | contribution = Random walks, universal traversal sequences, and the complexity of maze problems
 | doi = 10.1109/SFCS.1979.34
 | location = New York
 | mr = 598110
 | pages = 218–223
 | publisher = IEEE
 | title = [[Symposium on Foundations of Computer Science|Proceedings of 20th Annual Symposium on Foundations of Computer Science]]
 | year = 1979}}.</ref> False rejections are made with a small bounded probability that shrinks exponentially the longer the random walk is continued. This showed that '''SL''' is contained in [[RL (complexity)|RLP]], 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 that '''SL''' is contained in [[L/poly]], a non-uniform complexity class of the problems solvable deterministically in logarithmic space with polynomial [[advice (complexity)|advice]].

In 1989, Borodin et al. strengthened this result by showing that the [[complement (complexity)|complement]] of USTCON, determining whether two vertices are in different connected components, is also in '''RLP'''.<ref>{{citation
 | last1 = Borodin | first1 = Allan | author1-link = Allan Borodin
 | last2 = Cook | first2 = Stephen A. | author2-link = Stephen Cook
 | last3 = Dymond | first3 = Patrick W.
 | last4 = Ruzzo | first4 = Walter L.
 | last5 = Tompa | first5 = Martin
 | doi = 10.1137/0218038
 | issue = 3
 | journal = SIAM Journal on Computing
 | mr = 996836
 | pages = 559–578
 | title = Two applications of inductive counting for complementation problems
 | volume = 18
 | year = 1989| citeseerx = 10.1.1.394.1662}}.</ref> This placed USTCON, and '''SL''', in co-'''RLP''' and in the intersection of '''RLP''' and co-'''RLP''', which is [[ZPLP]], the class of problems which have log-space, expected polynomial-time, no-error randomized algorithms.

In 1992, [[Noam Nisan|Nisan]], [[Endre Szemerédi|Szemerédi]], and [[Avi Wigderson|Wigderson]] finally found a new deterministic algorithm to solve USTCON using only log<sup>1.5</sup> ''n'' space.<ref>{{citation
 | last1 = Nisan | first1 = Noam | author1-link = Noam Nisan
 | last2 = Szemerédi | first2 = Endre | author2-link = Endre Szemerédi
 | last3 = Wigderson | first3 = Avi | author3-link = Avi Wigderson
 | contribution = Undirected connectivity in O(log1.5n) space
 | doi = 10.1109/SFCS.1992.267822
 | pages = 24–29
 | title = Proceedings of 33rd Annual Symposium on Foundations of Computer Science
 | year = 1992}}.</ref> 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-'''SL'''.<ref>{{citation
 | last1 = Nisan | first1 = Noam | author1-link = Noam Nisan
 | last2 = Ta-Shma | first2 = Amnon
 | id = {{ECCC|1994|94|003}}
 | journal = Chicago Journal of Theoretical Computer Science
 | mr = 1345937
 | at = Article 1
 | title = Symmetric logspace is closed under complement
 | year = 1995}}.</ref> 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'''<sup>'''SL'''</sup> = '''SL'''; that is, a deterministic, log-space machine with an [[oracle machine|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 (complexity)|L]]'''.<ref>{{citation
 | last = Reingold | first = Omer | author-link = Omer Reingold
 | doi = 10.1145/1391289.1391291
 | issue = 4
 | journal = [[Journal of the ACM]]
 | mr = 2445014
 | pages = 1–24
 | title = Undirected connectivity in log-space
 | volume = 55
 | year = 2008}}.</ref> This paper used [[expander graph]]s 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 <math>O\text{(log } n \text {log log } n)</math> space—a weaker result—using different techniques.<ref>{{citation
 | last = Trifonov | first = Vladimir
 | doi = 10.1137/050642381
 | issue = 2
 | journal = [[SIAM Journal on Computing]]
 | mr = 2411031
 | pages = 449–483
 | title = An ''O''(log ''n'' log log ''n'') space algorithm for undirected ''st''-connectivity
 | volume = 38
 | year = 2008}}.</ref> 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 <math>64^{32}\,\log N</math> memory, and <math>O(N^{64^{32}})</math> time. This means that even for <math>N=2</math>, the algorithm would require more memory than contained on all computers in the world (a kiloexaexaexabyte).