User:Devanden/ST-Connectivity
Overview
[edit]ST Connectivity (Reachability) is a problem in computer science, specifically computational complexity theory of deciding if two vertices in a directed graph, labeled s and t are connected by a directed path. The problem is formally defined as follows:
ST Connectivity = {<D,s,t>: is a directed graph D with a path from vertex s to t }.
The algorithm for ST connectivity on graph D with n vertices outputs "yes" if there is a path between vertex s and t and "no" if no directed path exists. This algorithm is shown to be in log(n) time on non-deterministic Turing machines. The language is also shown to be NL-complete. The complement of ST Connectivity is called STNon-connectivity and is also shown to be in NL by Immerman-Szelepcsényi_Theorem. A related language is USTCON, which applies to undirected graphs.
Complexity
[edit]ST Connectivity ∈ NL. Which means that a Nondeterministic Turing machine can solve it in SPACE(log n)
ST Connectivity is also NL-complete. So, any algorithm ∈ NL reduces to ST Connectivity by a Log-space_reduction.
As a direct result of Savitch's theorem, the ST Connectivity algorithm can be simulated on a Deterministic Turing machine in SPACE(log2 n) (which is also in L).