Complexity Dojo/Savitch's Theorem

From Complexity Zoo
Revision as of 03:10, 18 November 2012 by Admin (talk | contribs) (1 revision: Complexity zoo import.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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 for a graph with nodes. As a corollary, we can apply the reachability method to show that NSPACESPACE. 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.


Proof: Let be a directed graph (given in the form of an adjacency matrix ), and let . We shall proceed by building up a predicate such that, for some vertices and natural number , if and only if there is a path of length at most connecting to . Then, , since any path longer than must visit some vertex twice.

To compute , we shall use a Turing machine with an input string and two work strings. The first work string will initially contain the a triple , where are represented as the indices of the vertices. Note that the length of this triple is . 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 triples will be needed.

shall work by noting that if for , then the path described has a midpoint . Formally, if and , there exists a node such that . Thus, to compute , will iterate through all vertices (using the second work tape) and check and 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 levels of recursion, we will be able to run this algorithm in 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 , NSPACE ⊆ SPACE.


Proof: Let be an NSPACE machine, and let be the number of tapes used by . We start by defining what we mean by a configuration of . We say that a configuration of is a tuple where is a state of , and where are strings over the tape alphabet of . We interpret a configuration as a "snapshot" of during its operation. Thus, given a configuration , we say that is in state and that each of the tapes contains the string , where the read head for that tape is between the two strings.

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

We can do better than simply stating that the configuration graph of is finite, though. Given a configuration , the number of choices for is limited to where is the set of states for . Moreover, by the definition of NSPACE, the total of the lengths of each string is bounded by . We can partition this length into the various strings with integers in the range . Thus, the number of choices for each configuration is bounded by , where is the tape alphabet of . Finally, the number of possible configurations of is bounded by for some constant depending only on .

Thus, we can run the algorithm for Reachability given above on the configuration graph of by performing a step of computation on whenever the algorithm would check if two verticies are adjacent or not. Performing that check requires space bounded by . Since there are vertices in the graph, Reachability for the initial and accepting configurations of can be computed in space bounded by . If , then this means that the space bound is . Finally, note that the algorithm for Reachability given above is deterministic. Hence, NSPACE ⊆ SPACE for all constructable , as claimed. ▪

As mentioned before, letting in the corollary be a polynomial gives that NPSPACE = PSPACE.