SL (complexity)

From Wikipedia, the free encyclopedia

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 we will discuss them together.

In October 2004 Omer Reingold showed that SL = L.

1 Origin
2 Complete problems
3 Important results
4 Consequences of L = SL
5 References
6 Footnotes

[edit] Origin

SL was first defined in 1982 by Lewis and Papadimitriou¹, who were looking for a class in which to place USTCON, which until this time could, at best, be placed only in NL, despite seeming not to require nondeterminism. They defined the symmetric Turing machine, used it to define SL, showed that USTCON was complete for SL, and proved that

$L \subseteq SL \subseteq NL$

where L is the more well-known class of problems solvable by an ordinary deterministic Turing machine in logarithmic space, and NL is the class of problems solvable by nondeterministic Turing machines in logarithmic space. The result of Reingold, discussed later, shows that in fact, when limited to log space, the symmetric Turing machine is equivalent in power to the deterministic Turing machine.

[edit] 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.

[edit] 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 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 DSPACE(log²n). ³

Although there were no 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 |V|³ time has passed (then reject)⁴. False rejections are made with a small bounded probability that shrinks exponentially the longer the random walk is continued. This also showed that SL is contained in RLP, the class of problems solvable in polynomial time and logarithmithic space with probabilistic machines that reject incorrectly less than 1/3 of the time.

In 1989, Borodin et al. strengthed this result by showing that the complement of USTCON, determining whether two vertices are in different connected components, is also in RLP. ⁵ 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, no-error randomized solutions and expected polynomial runtime.

In 1992, Nisan, Szemerédi, and Wigderson finally found a new deterministic algorithm to solve USTCON using only (log n)^1.5 space. ⁶ 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. ⁷ 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. In practice, this means it doesn't matter whether we use Turing reducibility or many-one reducibility to show a problem is in SL; they are equivalent. ⁸

A breakthrough October 2004 paper by Omer Reingold showed that USTCON is in fact in L. ⁹ Since USTCON is SL-complete, this implies that SL = L, essentially eliminating the usefulness of consideration of SL as a separate class.

[edit] 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.

[edit] References

Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. 20th Annual Symposium on Foundations of Computer Science, pp.218–223. San Juan, Puerto Rico. IEEE. October 1979.
A. Borodin, S. A. Cook, P. W. Dymond, W. L. Ruzzo, and M. Tompa. Two applications of inductive counting for complementation problems. SIAM Journal on Computing, v.18 n.3, p.559-578. June 1989.
Carme Àlvarez and Raymond Greenlaw. A Compendium of Problems Complete for Symmetric Logarithmic Space. Computational Complexity,pp.9:73–95. 2000.
Jesper Jansson. Deterministic Space-Bounded Graph Connectivity Algorithms. Manuscript. 1998.
Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science. pp.161-187. 1982.
Noam Nisan, Endre Szemerédi, and Avi Wigderson. Undirected Connectivity in O(log^1.5 n) space. In Proceedings 33rd Annual Symposium on Foundations of Computer Science. Pittsburgh, PA. IEEE. pp. 24-29. 1992.
Noam Nisan and Amnon Ta-Shma. Symmetric logspace is closed under complement. Chicago Journal of Theoretical Computer Science. 1995.
C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 0-201-53082-1.
Omer Reingold. Undirected ST-connectivity in Log-Space. Electronic Colloquium on Computational Complexity. No. 94.
W. J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. System Sci, 4, 2, pp. 177-192. 1970.
Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X.