Why Does Savitch's Theorem Square Space Complexity?

Savitch's theorem proves that any problem solvable by a non-deterministic Turing machine using a given amount of memory can also be solved by a deterministic Turing machine using at most the square of that memory. It achieves this by modeling the non-deterministic computation as a pathfinding problem in a graph of machine configurations and applying a recursive divide-and-conquer algorithm that reuses space across recursive calls.

Configuration Graphs and Reachability

A Turing machine's complete state at any moment—including its current control state, tape contents, and head positions—is called a configuration. If a non-deterministic Turing machine runs in space \(s(n) \ge \log n\) on an input of size \(n\), the total number of possible configurations is bounded by \(2^{O(s(n))}\).

We can represent the computation as a directed graph where each vertex is a configuration, and a directed edge exists from configuration \(u\) to configuration \(v\) if the machine can transition from \(u\) to \(v\) in a single step. Determining whether the machine accepts its input reduces to checking whether there is a directed path from the starting configuration \(c_{\text{start}}\) to an accepting configuration \(c_{\text{accept}}\) of length at most \(2^{O(s(n))}\).

The Recursive Midpoint Algorithm

A naive deterministic search, such as breadth-first or depth-first search, would need to store visited configurations to avoid cycles, which requires \(2^{O(s(n))}\) space—exponentially more than \(s(n)\). Savitch's algorithm avoids this by trading time for space using a recursive predicate \(\text{CAN-REACH}(u, v, k)\), which returns true if configuration \(v\) is reachable from configuration \(u\) in at most \(2^k\) steps.

The base case is \(k = 0\), where \(\text{CAN-REACH}(u, v, 0)\) is true if and only if \(u = v\) or there is a single-step transition from \(u\) to \(v\). For \(k > 0\), the algorithm checks every possible intermediate configuration \(w\) to see if both \(\text{CAN-REACH}(u, w, k - 1)\) and \(\text{CAN-REACH}(w, v, k - 1)\) hold:

\[\text{CAN-REACH}(u, v, k) = \bigvee_{w} \left( \text{CAN-REACH}(u, w, k - 1) \land \text{CAN-REACH}(w, v, k - 1) \right)\]

Crucially, the deterministic machine evaluates these two recursive calls sequentially. Once the first call \(\text{CAN-REACH}(u, w, k - 1)\) finishes, its memory is completely erased and reused for the second call \(\text{CAN-REACH}(w, v, k - 1)\).

Why the Space Bound Is Quadratic

Because the maximum path length in the configuration graph is \(2^{O(s(n))}\), the initial call uses \(k = O(s(n))\). Each recursive step decreases \(k\) by \(1\), so the maximum recursion depth is \(O(s(n))\).

At each level of the recursion stack, the algorithm only needs to store the current configurations \(u\), \(v\), and \(w\), along with the counter \(k\). Each configuration takes \(O(s(n))\) bits to represent. Multiplying the recursion depth \(O(s(n))\) by the \(O(s(n))\) space required per stack frame yields a total deterministic space complexity of \(O(s(n)^2)\).

Implications for Complexity Classes

Because squaring a polynomial still results in a polynomial, Savitch's theorem directly implies that \(\text{NSPACE}(s(n)) \subseteq \text{DSPACE}(s(n)^2)\) for any space-constructible function \(s(n) \ge \log n\). As a consequence, non-deterministic polynomial space equals deterministic polynomial space:

\[\text{NPSPACE} = \text{PSPACE}\]

This stands in sharp contrast to time complexity, where reusing resources is impossible and the relationship between \(\text{P}\) and \(\text{NP}\) remains open.