SL (complexity)
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 machine
s, 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 they are connected, and discussed together.
In October 2004 Omer Reingold
showed that SL = L
.
, 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
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.
problems. Some of the simplest and most important SL-complete problems they describe include:
The complement
s 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.
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 DSPACE(log2n). (Actually, Savitch's theorem gives the stronger result that NL is in DSPACE(log2n).)
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 |V|3 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 showed that SL is contained in 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
.
In 1989, Borodin et al. strengthened 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, expected polynomial-time, no-error randomized algorithms.
In 1992, Nisan, Szemerédi, and Wigderson finally found a new deterministic algorithm to solve USTCON using only log1.5 n 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 LSL = 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. 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.
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. A few weeks later, graduate student Vladimir Trifonov showed that USTCON could be solved deterministically using O(log n log log n) space—a weaker result—using different techniques.
s. It is also now known that a problem is in L if and only if it is log-space reducible to USTCON.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, SL (Symmetric Logspace or Sym-L) is the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
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
Connected component (graph theory)
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
. This problem is also called the undirected reachability problem. It does not matter whether many-one reducibility
Many-one reduction
In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.Many-one...
or Turing reducibility
Turing reduction
In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which solves A, assuming B is already known . It can be understood as an algorithm that could be used to solve A if it had available to it a subroutine for solving B...
is used. Although originally described in terms of symmetric Turing machine
Symmetric Turing machine
- Definition of Symmetric Turing machines :A Symmetric TM is a TM which has a configuration graph that is undirected. That is configuration i yields configuration j if and only if j yields...
s, 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
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
exists, which is complete for NL
NL (complexity)
In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space....
. Because USTCON is SL-complete, most advances that impact USTCON have also impacted SL. Thus they are connected, and discussed together.
In October 2004 Omer Reingold
Omer Reingold
Omer Reingold is a faculty member of the Foundations of Computer Science Group at the Weizmann Institute of Science, Israel. He received the 2005 Grace Murray Hopper Award for his work in finding a deterministic logarithmic-space algorithm for ST-connectivity in undirected graphs...
showed that SL = L
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
.
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 NLNL (complexity)
In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space....
, despite seeming not to require nondeterminism. They defined the symmetric Turing machine
Symmetric Turing machine
- Definition of Symmetric Turing machines :A Symmetric TM is a TM which has a configuration graph that is undirected. That is configuration i yields configuration j if and only if j yields...
, used it to define SL, showed that USTCON was complete for SL, and proved that
where L
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
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.
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 theoryGraph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
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 graphBipartite graphIn the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
, or equivalently, does it have a graph coloringGraph coloringIn graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
using 2 colors? - Do two undirected graphs have the same number of connected componentsConnected component (graph theory)In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three 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-satisfiabilityBoolean satisfiability problemIn computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
: given a formula requiring that xi xor xj hold for a number of pairs of variables (xi,xj), is there an assignment to the variables that makes it true?
The complement
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement...
s 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.
Important results
There are well-known classical algorithms such as depth-first searchDepth-first search
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
and breadth-first search
Breadth-first search
In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes...
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
Savitch's theorem
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, states that for any function ƒ ≥ log,...
, 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 DSPACE(log2n). (Actually, Savitch's theorem gives the stronger result that NL is in DSPACE(log2n).)
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 |V|3 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 showed that SL is contained in 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
L/poly
In computational complexity theory, L/poly is the complexity class of logarithmic space machines with a polynomial amount of advice. L/poly is a non-uniform logarithmic space class, analogous to the non-uniform polynomial time class P/poly....
, a non-uniform complexity class of the problems solvable deterministically in logarithmic space with polynomial advice
Advice (complexity)
In computational complexity theory, an advice string is an extra input to a Turing machine which is allowed to depend on the length n of the input, but not on input itself...
.
In 1989, Borodin et al. strengthened this result by showing that the complement
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its 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, expected polynomial-time, no-error randomized algorithms.
In 1992, Nisan, Szemerédi, and Wigderson finally found a new deterministic algorithm to solve USTCON using only log1.5 n 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 LSL = SL; that is, a deterministic, log-space machine with an oracle
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
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.
A breakthrough October 2004 paper by Omer Reingold
Omer Reingold
Omer Reingold is a faculty member of the Foundations of Computer Science Group at the Weizmann Institute of Science, Israel. He received the 2005 Grace Murray Hopper Award for his work in finding a deterministic logarithmic-space algorithm for ST-connectivity in undirected graphs...
showed that USTCON is in fact in L
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
. Since USTCON is SL-complete, this 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 O(log n log log n) space—a weaker result—using different techniques.
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 reductionLog-space reduction
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of pointers into the input, along with a logarithmic number of fixed-size integers...
s. It is also now known that a problem is in L if and only if it is log-space reducible to USTCON.