In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity.
, In other words, if a nondeterministic Turing machine can solve a problem using
space, a deterministic Turing machine can solve the same problem in the square of that space bound.
[1] Although it seems that nondeterminism may produce exponential gains in time (as formalized in the unproven exponential time hypothesis), Savitch's theorem shows that it has a markedly more limited effect on space requirements.
[2] The proof relies on an algorithm for STCON, the problem of determining whether there is a path between two vertices in a directed graph, which runs in
The basic idea of the algorithm is to solve recursively a somewhat more general problem, testing the existence of a path from a vertex
STCON is a special case of this problem where
is set large enough to impose no restriction on the paths (for instance, equal to the total number of vertices in the graph, or any larger value).
, a deterministic algorithm can iterate through all vertices
, and recursively search for paths of half the length from
This algorithm can be expressed in pseudocode (in Python syntax) as follows: Because each recursive call halves the parameter
, the number of levels of recursion is
bits of storage for its function arguments and local variables:
The total auxiliary space complexity is thus
The input graph is considered to be represented in a separate read-only memory and does not contribute to this auxiliary space bound.
Alternatively, it may be represented as an implicit graph.
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.
This algorithm can be applied to an implicit graph whose vertices represent the configurations of a nondeterministic Turing machine and its tape, running within a given space bound
The edges of this graph represent the nondeterministic transitions of the machine,
is set to the initial configuration of the machine, and
is set to a special vertex representing all accepting halting states.
In this case, the algorithm returns true when the machine has a nondeterministic accepting path, and false otherwise.
The number of configurations in this graph is
, from which it follows that applying the algorithm to this implicit graph uses space
Thus by deciding connectivity in a graph representing nondeterministic Turing machine configurations, one can decide membership in the language recognized by that machine, in space proportional to the square of the space used by the Turing machine.
Some important corollaries of the theorem include: