SL (complexity) - Complete Problems

Complete Problems

Using our definition, USTCON is trivially 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. Many of the problems are graph theory problems. 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-edge-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 x_i xor x_j hold for a number of pairs of variables (x_i,x_j), 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.

Now that we know L = SL, we know of a great deal more SL-complete problems with respect to log-space reductions: every 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.