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.
24-474: (Redirected from Sl ) [REDACTED] Look up SL in Wiktionary, the free dictionary. SL may refer to: Arts and entertainment [ edit ] SL (rapper) , a rapper from London Second Life , a multi-user 3D virtual world Sensei's Library , an Internet site dedicated to the game of Go Subdominant leittonwechselklänge Leica SL ,
48-594: A Korean auto parts company Rio Sul Serviços Aéreos Regionais (IATA code SL), a Brazilian airline Salt Lake City Southern Railroad (reporting mark SL) Stor-Oslo Lokaltrafikk , a public transport operator in Akershus, Norway Storstockholms Lokaltrafik , the public transport operator in Stockholm, Sweden Thai Lion Air (IATA airline code SL) Mercedes-Benz SL-Class , an automobile Trade unions [ edit ] Association of Social Educators ,
72-449: 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 where L is the more well-known class of problems solvable by an ordinary deterministic Turing machine in logarithmic space, and NL
96-663: A class of computational complexity Scientific Linux , a Linux distribution Service Loading , a variant of WAP push method Mathematics [ edit ] SL (complexity) , a class of computational complexity sl (elliptic function) , sine lemniscate function Special linear group in mathematics, denoted SL n or SL( n ) Special linear Lie algebra , denoted s l n ( F ) {\displaystyle {\mathfrak {sl}}_{n}(F)} or s l ( n , F ) {\displaystyle {\mathfrak {sl}}(n,F)} Other uses [ edit ] Serjeant-at-law ,
120-585: A compendium of them was made by Àlvarez and Greenlaw. Many of the problems are graph theory problems on undirected graphs. Some of the simplest and most important SL-complete problems they describe include: 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
144-501: A former type of barrister in England and Ireland Sine loco in bibliographies means that place of publication is unknown Sublingual administration of medicine Surround Left (SL) speaker on a 5.1 surround sound setup See also [ edit ] [REDACTED] Search for "SL" on Misplaced Pages. All pages with titles containing SL LS (disambiguation) SLS (disambiguation) Topics referred to by
168-577: A mirrorless system camera by Leica Camera AG Business and organizations [ edit ] Sociedad Limitada , the Spanish version of a private limited company Politics [ edit ] Serbian Left ( Srpska levica ), a political party in Serbia Stronnictwo Ludowe , a defunct Polish political party Soyons Libres , a French political party Transportation and vehicles [ edit ] SL Corporation ,
192-499: A practical formulation. It is explicit in his paper (and those leading up to it) that they are primarily concerned with asymptotics; as a result, the algorithm he describes would actually take 64 32 log N {\displaystyle 64^{32}\,\log N} memory, and O ( N 64 32 ) {\displaystyle O(N^{64^{32}})} time. This means that even for N = 2 {\displaystyle N=2} ,
216-436: A term used in taxonomy to mean "in the wider sense" of a definition Standard length , a common measurement for fish Abbreviation for × Sophrolaelia , an orchid genus Computing [ edit ] sl, a humorous command in some Unix -based systems that draws an animation of a steam locomotive, intended to be invoked as a typo of ls .sl , the country code top-level domain for Sierra Leone SL (complexity) ,
240-877: A trade union in Denmark Geography [ edit ] Sierra Leone , in West Africa, ISO 3166 code Saarland , a state of Germany SL postcode area of the United Kingdom Sungai Long , in Selangor, Malaysia Sri Lanka , an island country in South Asia Language [ edit ] Sl (digraph) , a Latin-script digraph Sign language , used by deaf persons Slovene language (ISO 639-1 code "sl") Science, technology, and mathematics [ edit ] Biology [ edit ] Sensu lato ,
264-407: 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. 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
SECTION 10
#1732783815243288-488: 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 . SL was first defined in 1982 by Harry R. Lewis and Christos Papadimitriou , who were looking for
312-536: 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 log n space. This was improved slightly, but there would be no more significant gains until Reingold. In 1995, Nisan and Ta-Shma showed
336-427: 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
360-525: Is different from Wikidata All article disambiguation pages All disambiguation pages SL">SL Too Many Requests If you report this error to the Wikimedia System Administrators, please include the details below. Request from 172.68.168.226 via cp1108 cp1108, Varnish XID 229427666 Upstream caches: cp1108 int Error: 429, Too Many Requests at Thu, 28 Nov 2024 08:50:15 GMT SL (complexity) USTCON
384-477: 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 ) . (Actually, Savitch's theorem gives the stronger result that NL is in DSPACE (log n ) .) Although there were no (uniform) deterministic space improvements on Savitch's algorithm for 22 years, a highly practical probabilistic log-space algorithm
408-645: Is in fact in L . This paper used expander graphs to guide the search through the input graph. Since USTCON is SL -complete, Reingold's result 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 ) {\displaystyle O{\text{(log }}n{\text{log log }}n)} space—a weaker result—using different techniques. There has not been substantial effort into turning Reingold's algorithm for USTCON into
432-475: 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. 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
456-427: The algorithm would require more memory than contained on all computers in the world (a kiloexaexaexabyte). 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
480-426: The most important corollaries of SL = co- SL is that L = 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. In 2004, a breakthrough paper by Omer Reingold showed that USTCON
504-401: The same term [REDACTED] This disambiguation page lists articles associated with the title SL . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=SL&oldid=1253677987 " Category : Disambiguation pages Hidden categories: Short description
SECTION 20
#1732783815243528-447: 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
552-478: 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,
576-512: 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 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
#242757