Savitch's theorem

Remarks

Let $N$ be a nondeterministic Turing machine that uses space $O(s(n))$. On an input of length $n$, it has at most $2^{c \, s(n)}$ configurations for some constant $c$. The deterministic machine checks whether an accepting configuration can be reached from the start within $2^{c \, s(n)}$ steps. To test reachability within $2^{t}$ steps, it tries every middle configuration and tests both halves within $2^{t-1}$ steps, reusing the same space. The recursion has depth $O(s(n))$ and each level stores one configuration of size $O(s(n))$, which gives space $O(s(n)^2)$. Walter Savitch proved the theorem in 1970.

Consequences: NPSPACE, defined with nondeterministic machines in polynomial space, equals PSPACE, since the square of a polynomial is a polynomial. Also $\mathrm{NL} \subseteq \mathrm{DSPACE}((\log n)^2)$, where NL is the class NL.

Going deeper

For a student

The theorem is a statement about reachability in the configuration graph, solved by divide and conquer on the path length. It shows that polynomial space is the same with or without nondeterminism, so there is no space analogue of the P versus NP question at the polynomial level. Whether the square is needed is open; for example, it is unknown whether $\mathrm{NL} = \mathrm{L}$. The Immerman–Szelepcsényi theorem gives a different fact about nondeterministic space: it is closed under complement.