Definitions for SL
This page provides all possible meanings and translations of the word SL
Shining Path, Sendero Luminoso, SL(noun)
a terrorist group formed in Peru in the late 1960s as a splinter group from the communist party of Peru; is among the most ruthless guerilla organizations in the world; seeks to destroy Peruvian institutions and replace them with a Maoist peasant regime; is involved in the cocaine trade
"Shining Path has been responsible for 30,000 deaths"
In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON, 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, 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.
Find a translation for the SL definition in other languages:
Select another language: