- St-connectivity
In
computer science andcomputational complexity theory , st-connectivity is adecision problem asking, for vertices "s" and "t" in adirected graph , if "t" is reachable from "s".Formally, the decision problem is given by "PATH = {
Complexity
The problem can be shown to be in NL, as a
non-deterministic Turing machine can guess the next node of the path, while the only information which has to be stored is which node is the node currently under consideration. The algorithm terminates if either the target node "t" is reached, or the path so far exceeds "m", the number of nodes in the graph.The complement of "st-connectivity", known as
st-non-connectivity , is also in the class NL, since "NL = coNL" by theImmerman-Szelepcsényi Theorem .In particular, the problem of "st-connectivity" is actually
NL-complete , that is, every problem in the class NL is reducible to connectivity under alog-space reduction . This remains true for the stronger case offirst-order reduction s (Immerman 1999, p. 51).Connectivity is solvable in deterministic
logspace , as per this paper. (Also,Savitch's theorem guarantees that the algorithm can be simulated in deterministic space.)The same problem for
undirected graph s is called "undirected s-t connectivity" and is log-space complete for the class SL, recently shown to be equal to L. On alternating graphs, the problem is complete for P.cite book | last = Immerman | first = Neil | authorlink = Neil Immerman | title = Descriptive Complexity | year = 1999 | publisher = Springer-Verlag | location = New York | id = ISBN 0-387-98600-6 | pages = 54 ]References
*cite book | author=Sipser, Michael | title=Introduction to the Theory of Computation | publisher=Thompson Course Technology | year=2006 | id=ISBN 0-534-95097-3
*cite book | last = Immerman | first = Neil | authorlink = Neil Immerman | title = Descriptive Complexity | year = 1999 | publisher = Springer-Verlag | location = New York | id = ISBN 0-387-98600-6ee also
Wikimedia Foundation. 2010.
