Notes - Computational Complexity HT25, Savitch's theorem

Created: February 13, 2025
Updated: February 13, 2025

Savitch’s theorem states that for a space-constructible $S$, then

\[\mathsf{NSPACE}(S) \subseteq \mathsf{DSPACE}(S^2)\]

This is quite remarkable – it shows that you can simulate any space-bounded non-deterministic Turing machine by using a deterministic Turing machine that uses quadratically more space. One consequence of this is that

\[\mathsf{PSPACE} = \mathsf{NPSPACE}\]

which can be seen as a space version of the famous $\mathsf{P} \stackrel?= \mathsf{NP}$ question.

Flashcards

@State Savitch’s theorem, a result about a different relationship between $\mathsf{NSPACE}$ and $\mathsf{DSPACE}$.

If $S$ is space-constructible, then

\[\mathsf{NSPACE}(S) \subseteq \mathsf{DSPACE}(S^2)\]

@Prove Savitch’s theorem, i.e. that if $S$ is space-constructible then

\[\mathsf{NSPACE}(S) \subseteq \mathsf{DSPACE}(S^2)\]

Let $N$ be an NTM deciding a language $A$ in space $S$. We proceed by a simulation argument, showing that there is a deterministic TM $M$ that can decide $A$ in space $S^2$.

Let $w$ be a string considered as input to $N$. For configurations $c _ 1$ and $c _ 2$ of $N$ and an integer $t$, we construct a procedure $\mathbf{CanYield}(c _ 1, c _ 2, t)$ which outputs $\mathit{accept}$ if $N$ can go from configuration $c _ 1$ to configuration $c _ 2$ in $t$ or fewer steps along some nondeterministic path, and otherwise $\mathit{rejects}$. We may assume $t$ is a power of two, and implement this recursively as follows:

  • $\mathbf{CanYield}(c _ 1, c _ 2, t)$
    • If $t = 1$, then test directly whether $c _ 1 = c _ 2$ or whether $c _ 1$ yields $c _ 2$ in one step according to the rules of $N$. Accept if either test succeeds and reject otherwise.
    • If $t > 1$, then for each configuration $c _ m$ of $N$ using space $s(n)$:
      • Run $\mathbf{CanYield}(c _ 1, c _ m, t/2)$
      • Run $\mathbf{CanYield}(c _ m, c _ 2, t/2)$
      • If steps 3 and 4 both accept, then accept.
    • If haven’t yet accepted, reject.

We may also assume that when $N$ accepts, it clears its tape and moves the head to the leftmost cell, therefore entering a unique configuration called $c _ \text{accept}$.

This means we can define $M$ as follows:

Let $c _ \text{start}$ be the start configuration of $N$ on $w$. Select a constant $d$ so that $N$ has no more than $2^{dS(n)}$ configurations using $S(n)$ space, where $n = \vert w \vert $. Hence $2^{dS(n)}$ provides an upper bound on the running time of any branch of $N$ on $w$ (this is effectively the result that $\mathsf{NSPACE}(S) \subseteq \mathsf{DTIME}(2^{O(S)}))$. Then

  • $\mathbf M(w)$:
    • Output the result of $\mathbf{CanYield}(c _ \text{start}, c _ \text{accept}, 2^{dS(n)})$.

This means $M$ simulates $N$, and so it remains to prove that $M$ halts within $S^2$ space.

Whenever $\mathbf{CanYield}$ invokes itself recursively, it stores $\langle m, c _ 1, c _ 2, t \rangle$ on a stack, where $m$ is the index of the configuration being considered, so that these values may be restored upon return from the recursive invocation.

Each level of the recursion then uses $O(S(n))$ additional space (since each $c _ i$ has size $O(S(n))$. Furthermore, each level of the recursion divides the size of $t$ in half. Initially $t$ starts out equal to $2^{dS(n)}$, so the depth of the recursion is $O(\log 2^{dS(n)})$, or $O(S(n))$. Therefore the total space used in the call to $\mathbf{CanYield}$ is $O(S(n)^2)$.



Related posts