|
USTCON
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 (graph theory), connected component. This problem is also called the undirected reachability problem. It does not matter whether many-one reduction, many-one reducibility or Turing reduction, 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 (complexity), NL. Because US ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Symmetric Turing Machine
A symmetric Turing machine is a Turing machine which has a configuration graph that is undirected (that is, configuration i yields configuration j if and only if j yields i). Definition of symmetric Turing machines Formally, we define a variant of Turing machines with a set of transitions of the form , where ''p,q'' are states, ''ab,cd'' are pairs of symbols and ''D'' is a direction. If ''D'' is ''left'', then the head of a machine in state ''p'' above a tape symbol ''b'' preceded by a symbol ''a'' can be transitioned by moving the head left, changing the state to ''q'' and replacing the symbols ''a,b'' by ''c,d''. The opposite transition can always be applied. If ''D'' is right the transition is analogous. The ability to peek at two symbols and change both at a time is non-essential, but makes the definition easier. Such machines were first defined in 1982 by Harry R. Lewis and Christos Papadimitriou, who were looking for a class in which to place USTCON, the problem askin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |