Overview

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 path. Wikibooks Wikiversity has more about this subject: School of Computer Science Open Directory Project: Computer Science Downloadable Science and Computer Science books Collection of Computer Science Bibliographies Belief that title science in computer science is inappropriate Categories: Computer science ... Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... A graph with 6 vertices (nodes) and 7 edges. ... In mathematics, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the successor vertex. ...

Definition

ST Connectivity is a language formally defined as:
ST Connectivity=.

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 NL. The complement of ST Connectivity is called STNon-connectivity and is also shown to be in NL by the Immerman-Szelepcsényi Theorem. In mathematics, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the successor vertex. ... In mathematics, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the successor vertex. ... In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. ... In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. ...

Complexity

It is known that 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(log² n). In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. ... In theoretical computer science, an ordinary (deterministic) Turing machine has a transition rule that specifies for a given current state of the head and computer (s,q) a single instruction (s, q, d), where s is the symbol to be written by the head, q is the subsequent state of... In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. ... In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. ... In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. ... In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. ... Overview In computational complexity theory, Savitchs theorem, proved by Walter Savitch in 1970, states that for any function f(n) ≥ log(n) NSPACE(f(n)) ⊆ DSPACE(f²(n)). In other words, if a nondeterministic Turing machine can solve a problem using f(n) space, an ordinary deterministic Turing machine... The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ...