Computational Complexity HT25, Savitch's theorem

Created: February 13, 2025 | Updated: May 11, 2025 | About these notes | View in context | Study these flashcards

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.

If $S$ is space-constructible and $S(n) \ge \log(n)$, then

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

Savitch’s theorem states that

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

for some class of functions $S$. What are the two requirements on $S$?
  • $S$ is space-constructible
  • $S(n) \ge \log(n)$

@Prove Savitch’s theorem, i.e. that if $S$ is space-constructible and $S(n) \ge n$, then

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

(Savitch’s theorem also also under the more general condition that $S(n) \ge \log n$, briefly note at the end of the proof how you would you about proving this).

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

The problem in the $S(n) \le n$ case is that each configuration contains a copy of the input $w$ and $ \vert w \vert = n$, so you cannot guarantee that the final space usage is only $O(S(n)^2)$. To fix this, suppose that the input tape of the TM $M$ is read-only and rather than storing configurations, storing “configurations of $M$ on $w$”, which do not include $w$ (any step requiring information about $w$ that would be in the configuration can just read it from the input tape). Then each configuration is $\log (n 2^{O(f(n))}) = \log n + O(f(n))$ space, so if $f(n) \ge \log n$, then this is just $O(f(n))$.



Related posts