In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, Savitch's theorem, proved by
Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic
space complexity. It states that for any function
,
:
In other words, if a
nondeterministic Turing machine can solve a problem using
space, a
deterministic Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer alg ...
can solve the same problem in the square of that space bound.
[Arora & Barak (2009) p.86] 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.
[Arora & Barak (2009) p.92]
Proof
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
space for
vertices. The basic idea of the algorithm is to solve
recursively a somewhat more general problem, testing the existence of a path from a vertex
to another vertex
that uses at most
edges, for a parameter
given as input. 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). To test for a
-edge path from
to
,
a nondeterministic algorithm can guess the identity of a middle vertex
of the path, and recursively search for paths of half the length from
to
and from
to
.
This algorithm can be expressed in pseudocode (in
Python syntax) as follows:
def stcon(s, t) -> bool:
"""Test whether a path of any length exists from s to t"""
return k_edge_path(s, t, n) # n is the number of vertices
def k_edge_path(s, t, k) -> bool:
"""Test whether a path of length at most k exists from s to t"""
if k 0:
return s t
if k 1:
return (s, t) in edges
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
Because each recursive call halves the parameter
, the number of levels of recursion is
. Each level requires
bits of storage for its function arguments and
local variables:
and the vertices
,
, and
require
bits each. 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
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer alg ...
.
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.
-------
Corollaries
Some important corollaries of the theorem include:
;
PSPACE =
NPSPACE
: That is, the languages that can be recognized by deterministic polynomial-space Turing machines and nondeterministic polynomial-space Turing machines are the same. 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 and
NP, although this is still an
open question.
;
NL ⊆
L2
: That is, all languages that can be solved nondeterministically in logarithmic space can be solved deterministically in the complexity class
This follows from the fact that STCON is
NL-complete.
See also
*
Immerman–Szelepcsényi theorem
In computational complexity theory, the Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation. It was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for wh ...
Notes
References
*
*
*
*{{citation
, last = Sipser
, first = Michael
, author-link = Michael Sipser
, contribution = Section 8.1: Savitch's Theorem
, isbn = 0-534-94728-X
, pages
279–281 , publisher = PWS Publishing
, title = Introduction to the Theory of Computation
, year = 1997
, url-access = registration
, url = https://archive.org/details/introductiontoth00sips/page/279
External links
* Lance Fortnow,
'. Accessed 09/09/09.
*
Richard J. Lipton,
Savitch’s Theorem'. Gives a historical account on how the proof was discovered.
Structural complexity theory
Theorems in computational complexity theory