Editing SL (complexity) (section)

== Complete problems ==

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.<ref>{{citation
 | last1 = Àlvarez | first1 = Carme
 | last2 = Greenlaw | first2 = Raymond
 | doi = 10.1007/PL00001603
 | issue = 2
 | journal = Computational Complexity
 | mr = 1809688
 | pages = 123–145
 | title = A compendium of problems complete for symmetric logarithmic space
 | volume = 9
 | year = 2000}}.</ref> Many of the problems are [[graph 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 there ''k'' paths between two vertices, sharing vertices only at the endpoints? (a generalization of USTCON, equivalent to asking whether a graph 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 component (graph theory)|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 forest]]s 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-[[Boolean satisfiability problem|satisfiability]]: given a formula requiring that <math>x_i</math> or <math>x_j</math> hold for a number of pairs of variables <math>(x_i,x_j)</math>, is there an assignment to the variables that makes it true?

The [[complement (complexity)|complement]]s 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.