In computational complexity theory, 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 \( f\in \Omega (\log(n)) \),
\( {\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right).} \_
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.[1] 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.[2]
Proof
There is a proof of the theorem that is constructive: it demonstrates an algorithm for STCON, the problem of determining whether there is a path between two vertices in a directed graph, which runs in \( O\left((\log n)^{2}\right) \) space for n 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 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. Using pseudocode (with syntax closely resembling Python) we can express this algorithm as follows:
def k_edge_path(s, t, k) -> bool:
"""Savitch's theorem."""
if k == 0:
return s == t
if k == 1:
return s == t or (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
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 variables at that level, so the total space used by the algorithm is \( O\left((\log n)^{2}\right) \). 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.
The reason this algorithm implies the theorem is that any language \( {\displaystyle L\in {\mathsf {NSPACE}}\left(f\left(n\right)\right)} \) corresponds to a directed graph whose vertices are the \( {\displaystyle 2^{O\left(f(n)\right)}} \) configurations of a Turing machine deciding membership in L. For each \( x\in \{0,1\}^{n} \), this graph has a path from the starting configuration on input x to the accepting configuration if and only if \( x\in L \). Thus deciding connectivity is sufficient to decide membership in L, and by the above algorithm this can be done in \( {\displaystyle {\mathsf {DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right)} \).
Corollaries
Some important corollaries of the theorem include:
PSPACE = 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 and NP, although this is still an open question.
NL ⊆ L2
STCON is NL-complete, and so all languages in NL are also in the complexity class \( {\displaystyle {\mathsf {\color {Blue}L}}^{2}={\mathsf {DSPACE}}\left(\left(\log n\right)^{2}\right)}. \)
See also
Exponential time hypothesis
Immerman–Szelepcsényi theorem
Notes
Arora & Barak (2009) p.86
Arora & Barak (2009) p.92
References
Arora, Sanjeev; Barak, Boaz (2009), Computational complexity. A modern approach, Cambridge University Press, ISBN 978-0-521-42426-4, Zbl 1193.68112
Papadimitriou, Christos (1993), "Section 7.3: The Reachability Method", Computational Complexity (1st ed.), Addison Wesley, pp. 149–150, ISBN 0-201-53082-1
Savitch, Walter J. (1970), "Relationships between nondeterministic and deterministic tape complexities", Journal of Computer and System Sciences, 4 (2): 177–192, doi:10.1016/S0022-0000(70)80006-X, hdl:10338.dmlcz/120475
Sipser, Michael (1997), "Section 8.1: Savitch's Theorem", Introduction to the Theory of Computation, PWS Publishing, pp. 279–281, ISBN 0-534-94728-X
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
