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,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 $(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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} and that each of the tapes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i\in[1..k]} contains the string Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_M} where each vertex is a possible configuration of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} , since there are a finite number of possible configurations reachable by a machine with bounded space. For each pair of configurations Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A, B\in G_M} , there is an edge in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_M} from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} if and only if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} can be reached from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} in one step of computation.

We can do better than simply stating that the configuration graph of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} is finite, though. Given a configuration Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (q, x_1, y_1, \dots, x_k, y_k)} , the number of choices for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} is limited to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\vert Q\right\vert} where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q} is the set of states for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} . Moreover, by the definition of NSPACE, the total of the lengths of each string Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i,y_i} is bounded by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)} . We can partition this length into the various strings with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2k} integers in the range Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [0..f(n)]} . Thus, the number of choices for each configuration is bounded by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\vert Q\right\vert \left\vert\Sigma\right\vert^{2k\cdot f(n)}} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma} is the tape alphabet of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} . Finally, the number of possible configurations of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} is bounded by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle nc^{f(n)}=c^{\log n + f(n)}} for some constant Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} depending only on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} .

Thus, we can run the algorithm for Reachability given above on the configuration graph of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} by performing a step of computation on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} whenever the algorithm would check if two verticies are adjacent or not. Performing that check requires space bounded by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(f(n))} . Since there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(c^{\log n + f(n)})} vertices in the graph, Reachability for the initial and accepting configurations of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} can be computed in space bounded by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log^2 (c^{\log n + f(n})) = O(f^2(n) + \log^2 n)} . If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log(n) = o(f(n))} , then this means that the space bound is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(f^2(n))} . Finally, note that the algorithm for Reachability given above is deterministic. Hence, NSPACEFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (f(n))} ⊆ SPACEFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (f^2(n))} for all constructable Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = \omega(\log n)} , as claimed. ▪

As mentioned before, letting Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)} in the corollary be a polynomial gives that NPSPACE = PSPACE.