# 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 ,

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[edit]

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 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):
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 . 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 corresponds to a directed graph whose vertices are the configurations of a Turing machine deciding membership in L. For each , this graph has a path from the starting configuration on input x to the accepting configuration if and only if . Thus deciding connectivity is sufficient to decide membership in L, and by the above algorithm this can be done in .

## Corollaries[edit]

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
^{2}- STCON is NL-complete, and so all languages in NL are also in the complexity class .

## See also[edit]

## Notes[edit]

## References[edit]

- 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 - 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[edit]

- 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.