is k-connected) Is a given graph a bipartite graph, or equivalently, does it have a graph coloring using 2 colors? Do two undirected graphs have the same number of connected components? Does a graph have an even number of connected components? Given a graph, is there a cycle containing a given edge? Do the spanning 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 the minimum weight spanning forest? Exclusive or 2-satisfiability: given a formula requiring that or hold for a number of pairs of variables , is there an assignment to the variables that makes it true? The complements of all these problems are in SL as well, since, as we will see, SL is closed under complement. 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. 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 log2 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 . (Actually, Savitch's theorem gives the stronger result that NL is in .) 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 time has passed (then reject). False rejections are made with a small bounded probability that shrinks exponentially the longer the