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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle b} . Then, Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathrm {Reachability} (a,b)=\mathrm {Path} (a,b,n)} , 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (a,b,i)} , where $a,b$ are represented as the indices of the vertices. Note that the length of this triple is Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle O(\left\lceil \log n\right\rceil )} triples will be needed.

$M$ shall work by noting that if $\mathrm {Path} (a,b,i)$ for Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle i>0} , then the path described has a midpoint $z$. Formally, if $\mathrm {Path} (a,b,i)$ and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle i>0} , there exists a node $z$ such that Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle z\in V} (using the second work tape) and check Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathrm {Path} (a,z,i-1)} and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x_{i}y_{i}} , where the read head for that tape is between the two strings.

We can build a graph Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle O(\log ^{2}(c^{\log n+f(n}))=O(f^{2}(n)+\log ^{2}n)} . If Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \log(n)=o(f(n))} , then this means that the space bound is Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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.