Complexity Dojo/Savitch's Theorem

Main Zoo - Complexity Garden - Zoo Glossary - Zoo References - Chris' Complexity Dojo

---

Major Theorems: Cook-Levin - Savitch's - Ladner's - Blum Speedup - Impagliazzo-Widgerson - Toda's - Natural Proofs

Proof Techniques: Diagonalization

Savitch's Theorem shows that the Reachability problem can be solved in space $O(\log ^{2}n)$ for a graph with $n$ nodes. As a corollary, we can apply the reachability method to show that NSPACE$(f(n))$ ⊆ SPACE$(f^{2}(n))$. This in turn gives us immediately that NPSPACE = PSPACE; that is, that for polynomially-bounded space, non-determinism doesn't buy us anything, in contrast to what we suspect about polynomially-bounded time.

Theorem (Savitch's Theorem). Reachability ∈ SPACE$(\log ^{2}n)$.

---

Proof: Let $G=(V,E)$ be a directed graph (given in the form of an adjacency matrix $A^{G}$), and let $n=\left\vert V\right\vert$. We shall proceed by building up a predicate $\mathrm {Path} :V\times V\times \mathbb {N} \to \{0,1\}$ such that, for some vertices $a,b$ and natural number $i$, $\mathrm {Path} (a,b,i)=1$ if and only if there is a path of length at most $2^{i}$ connecting $a$ to $b$. Then, $\mathrm {Reachability} (a,b)=\mathrm {Path} (a,b,\left\lceil \log n\right\rceil )$, since any path longer than $n$ must visit some vertex twice.

To compute $\mathrm {Path} (a,b,i)$, we shall use a Turing machine $M$ with an input string $A^{G}$ and two work strings. The first work string will initially contain the a triple $(a,b,i)$, where $a,b$ are represented as the indices of the vertices. Note that the length of this triple is $O(\left\lceil \log n\right\rceil )$. During the course of the algorithm, we shall add additional triples of the same form for intermediate problems. We shall see soon that no more than $O(\left\lceil \log n\right\rceil )$ triples will be needed.

$M$ shall work by noting that if $\mathrm {Path} (a,b,i)$ for $i>0$, then the path described has a midpoint $z$. Formally, if $\mathrm {Path} (a,b,i)$ and $i>0$, there exists a node $z$ such that $\mathrm {Path} (a,z,i-1)\wedge \mathrm {Path} (z,b,i-1)$. Thus, to compute $\mathrm {Path} (a,b,i)$, $M$ will iterate through all vertices $z\in V$ (using the second work tape) and check $\mathrm {Path} (a,z,i-1)$ and $\mathrm {Path} (z,b,i-1)$ recursively, using the first work tape as a stack to store which sub-problem we're working on. Since we'll never need more than $\log n$ levels of recursion, we will be able to run this algorithm in $O(\log ^{2}n)$ space, as claimed. ▪

In and of itself, this theorem hides its true importance. The true power of the theorem comes when we apply it to the configuration graph of an NSPACE machine.

Corollary. For all constructable $f(n)=\omega (\log n)$, NSPACE$(f(n))$ ⊆ SPACE$(f^{2}(n))$.

---

Proof: Let $M$ be an NSPACE$(f(n))$ machine, and let $k$ be the number of tapes used by $M$. We start by defining what we mean by a configuration of $M$. We say that a configuration of $M$ is a $2k+1$ tuple $(q,x_{1},y_{1},\dots ,x_{k},y_{k})$ where $q$ is a state of $M$, and where $x_{i},y_{i}$ are strings over the tape alphabet of $M$. We interpret a configuration as a "snapshot" of $M$ during its operation. Thus, given a configuration $(q,x_{1},y_{1},\dots ,x_{k},y_{k})$, we say that $M$ is in state $q$ and that each of the tapes $i\in [1..k]$ contains the string $x_{i}y_{i}$, where the read head for that tape is between the two strings.

We can build a graph $G_{M}$ where each vertex is a possible configuration of $M$, since there are a finite number of possible configurations reachable by a machine with bounded space. For each pair of configurations $A,B\in G_{M}$, there is an edge in $G_{M}$ from $A$ to $B$ if and only if $B$ can be reached from $A$ in one step of computation.

We can do better than simply stating that the configuration graph of $M$ is finite, though. Given a configuration $(q,x_{1},y_{1},\dots ,x_{k},y_{k})$, the number of choices for $q$ is limited to $\left\vert Q\right\vert$ where $Q$ is the set of states for $M$. Moreover, by the definition of NSPACE, the total of the lengths of each string $x_{i},y_{i}$ is bounded by $f(n)$. We can partition this length into the various strings with $2k$ integers in the range $[0..f(n)]$. Thus, the number of choices for each configuration is bounded by $\left\vert Q\right\vert \left\vert \Sigma \right\vert ^{2k\cdot f(n)}$, where $\Sigma$ is the tape alphabet of $M$. Finally, the number of possible configurations of $M$ is bounded by $nc^{f(n)}=c^{\log n+f(n)}$ for some constant $c$ depending only on $M$.

Thus, we can run the algorithm for Reachability given above on the configuration graph of $M$ by performing a step of computation on $M$ whenever the algorithm would check if two verticies are adjacent or not. Performing that check requires space bounded by $O(f(n))$. Since there are $O(c^{\log n+f(n)})$ vertices in the graph, Reachability for the initial and accepting configurations of $M$ can be computed in space bounded by $O(\log ^{2}(c^{\log n+f(n}))=O(f^{2}(n)+\log ^{2}n)$. If $\log(n)=o(f(n))$, then this means that the space bound is $O(f^{2}(n))$. Finally, note that the algorithm for Reachability given above is deterministic. Hence, NSPACE$(f(n))$ ⊆ SPACE$(f^{2}(n))$ for all constructable $f(n)=\omega (\log n)$, as claimed. ▪

As mentioned before, letting $f(n)$ in the corollary be a polynomial gives that NPSPACE = PSPACE.