Savitch's theorem

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 ${\displaystyle f\in \Omega (\log(n))}$,

${\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(f\left(n\right)^{2}\right).}$

In other words, if a nondeterministic Turing machine can solve a problem using ${\displaystyle f(n)}$ 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, this theorem shows that it has a markedly more limited effect on space requirements.^[2]

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 ${\displaystyle O\left((\log n)^{2}\right)}$ space for ${\displaystyle 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 s-t path, by recursively searching for paths of half the length from s to u and u to t. Using pseudocode (in Python syntax) we can express this algorithm as follows:

def k_edge_path(s, t, k) -> bool:
    """k initially equals n (which is the number of vertices)"""
    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

This search calls itself to a recursion depth of ${\displaystyle O(\log n)}$ levels, each of which requires ${\displaystyle O(\log n)}$ bits to store the function arguments and local variables at that level: k and all vertices (s, t, u) require ${\displaystyle O(\log n)}$ bits each. The total auxiliary space complexity is thus ${\displaystyle O\left((\log n)^{2}\right)}$.^{[Note 1]} 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.

To see why this algorithm implies the theorem, consider the following. For any language ${\displaystyle L\in {\mathsf {NSPACE}}(f(n))}$, there is a Turing machine ${\displaystyle M}$ which decides ${\displaystyle L}$ in space ${\displaystyle f(n)}$. Assume w.l.o.g. the alphabet is a binary alphabet ${\displaystyle \{0,1\}}$ (viz. ${\displaystyle L\subseteq \{0,1\}^{*}}$). For any input word ${\displaystyle x\in \{0,1\}^{*}}$, there is a directed graph ${\displaystyle G_{x}^{M}}$ whose vertices are the configurations of ${\displaystyle M}$ when running on the input ${\displaystyle x}$. There may be infinitely many such configurations; e.g. when ${\displaystyle M}$ keeps writing a symbol on the tape and moving the head to the right in a loop, ad infinitum. The configurations then grow arbitrarily large. However, we know that at most ${\displaystyle f\left(n\right)}$ space is needed to decide whether ${\displaystyle x\in L}$, so we only care about configurations of size at most ${\displaystyle f\left(n\right)}$; call any such configuration admissible. There are finitely many admissible configurations; namely ${\displaystyle 2^{O\left(f(n)\right)}}$. Therefore, the induced subgraph ${\displaystyle [G_{x}^{M}]}$ of ${\displaystyle G_{x}^{M}}$ containing (exactly) the admissible configurations has ${\displaystyle 2^{O\left(f(n)\right)}}$ vertices. For each input ${\displaystyle x\in \{0,1\}^{n}}$, ${\displaystyle [G_{x}^{M}]}$ has a path from the starting configuration to an accepting configuration if and only if ${\displaystyle x\in L}$. Thus by deciding connectivity in ${\displaystyle [G_{x}^{M}]}$, we can decide membership of ${\displaystyle x}$ in ${\displaystyle L}$. By the above algorithm this can be done deterministically in space ${\displaystyle O\left(\left(\log 2^{O\left(f(n)\right)}\right)^{2}\right)=O\left(f\left(n\right)^{2}\right)}$; hence ${\displaystyle L}$ is in ${\displaystyle {\mathsf {DSPACE}}\left(f\left(n\right)^{2}\right)}$.

Since this holds for all ${\displaystyle f\in \Omega (\log n)}$ and all ${\displaystyle L\in {\mathsf {NSPACE}}\left(f\left(n\right)\right)}$, we get the statement of the theorem:

For all functions ${\displaystyle f\in \Omega (\log n)}$, ${\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(f\left(n\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 ⊆ L²
  • 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[]

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

External links[]

• Lance Fortnow, Foundations of Complexity, Lesson 18: Savitch's Theorem. Accessed 09/09/09.
• Richard J. Lipton, Savitch’s Theorem. Gives a historical account on how the proof was discovered.