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

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 ∈ SPACEFailed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (\log ^{2}n)} .

Proof: Let $G=(V,E)$ be a directed graph (given in the form of an adjacency matrix Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A^{G}} ), and let Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n=\left\vert V\right\vert } . We shall proceed by building up a predicate Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathrm {Path} :V\times V\times \mathbb {N} \to \{0,1\}} such that, for some vertices $a,b$ and natural number $i$ , Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathrm {Path} (a,b,i)=1} if and only if there is a path of length at most Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2^{i}} connecting $a$ to $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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathrm {Path} (a,b,i)} , we shall use a Turing machine $M$ with an input string Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 $\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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2k+1} tuple Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (q,x_{1},y_{1},\dots ,x_{k},y_{k})} where $q$ is a state of $M$ , and where Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (q,x_{1},y_{1},\dots ,x_{k},y_{k})} , the number of choices for $q$ is limited to Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x_{i},y_{i}} is bounded by Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(n)} . We can partition this length into the various strings with Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2k} integers in the range Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle [0..f(n)]} . Thus, the number of choices for each configuration is bounded by Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(n)=\omega (\log n)} , as claimed. ▪

As mentioned before, letting Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(n)} in the corollary be a polynomial gives that NPSPACE = PSPACE.

Complexity Dojo/Savitch's Theorem

Navigation menu

Search