Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
Walter John Savitch is best known for discovering the complexity class NL , and for Savitch's theorem which defines a relationship between the NSPACE and DSPACE complexity classes. His work in establishing complexity classes has helped to create the background against which non-deterministic and...
in 1970, states that for any function ƒ(n) ≥ log(n),
In other words, if a nondeterministic Turing machine can solve a problem using f(n) space, an ordinary deterministic Turing machine can solve the same problem in the square of that space bound. Although it seems that nondeterminism may produce exponential gains in time, this theorem shows that it has a markedly more limited effect on space requirements.
Proof
The proof of the theorem is constructive: it demonstrates an algorithm for STCON
ST-connectivity
In computer science and computational complexity theory, st-connectivity or STCON is a decision problem asking, for vertices s and t in a directed graph, if t is reachable from s.Formally, the decision problem is given by- Complexity :...
, the problem of determining whether there is a path between two vertices in a directed graph, which runs in space for n vertices. The basic idea of the algorithm is to solve recursively
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
a somewhat more general problem, testing the existence of a path from a vertex s to another vertex t that uses at most k edges, where k is a parameter that is given as input to the recursive algorithm; STCON may be solved from this problem by setting k to n. To test for a k-edge path from s to t, one may test whether each vertex u may be the midpoint of the path, by recursively searching for paths of half the length from s to u and u to t.
In pseudocode:
def k_edge_path(s, t, k):
if k
0:
return s
t
else if k
1:
return s
t or (s, t) in edges
else:
for u in vertices:
if k_edge_path(s, u, floor(k / 2)) and k_edge_path(u, t, ceil(k / 2)):
return true
return false
This search calls itself to a recursion depth of O(log n) levels, each of which requires O(log n) bits to store the function arguments and local variable
Local variable
In computer science, a local variable is a variable that is given local scope. Such a variable is accessible only from the function or block in which it is declared. In programming languages with only two levels of visibility, local variables are contrasted with global variables...
s at that level, so the total space used by the algorithm is . Although described above in the form of a program in a high-level language, the same algorithm may be implemented with the same asymptotic space bound on a Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
In computational complexity theory, NL-Complete is a complexity class which is complete for NL. It contains the most "difficult" or "expressive" problems in NL...
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....
are also in the complexity class , which is often abbreviated as L
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
2.
Corollaries
Some important corollaries of the theorem include:
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
= NPSPACE
This follows directly from the fact that the square of a polynomial function is still a polynomial function. It is believed that a similar relationship does not exist between the polynomial time complexity classes, P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
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, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
Richard Jay "Dick" Lipton is an American computer scientist who has worked in computer science theory, cryptography, and DNA computing. Lipton is presently Associate Dean of Research, Professor, and the Frederick G...
, Savitch’s Theorem. Gives a historical account on how the proof was discovered.
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
space for n vertices. The basic idea of the algorithm is to solve recursively
. Although described above in the form of a program in a high-level language, the same algorithm may be implemented with the same asymptotic space bound on a Turing machine
, which is often abbreviated as L