Foundations of Complexity Lesson 18: Savitch's Theorem

Unlike what we believe for time, there is a polynomial relation between deterministic and nondeterministic space.

Savitch's Theorem (1970): NSPACE(s(n)) is contained in DSPACE(s²(n))

Proof: Recall the definition of tableau (as described in Lesson12). Let N be a nondeterministic machine that uses s(n) space. We can represent the computation of an input x of length n by a tableau where each configuration has size O(s(n)) and there are at most m = c^s(n) configurations for some constant c.

We will create a deterministic machine M(x) to determine whether the tableau is proper and thus N(x) accepts. First we need a subroutine CHECK to determine whether one configuration can reach another in 2^t steps. We do not have enough space to write the entire tableau but instead we do a divide and conquer approach: Try all possible middle configurations and recurse on each half.

CHECK(CONF1,CONF2,t)
\* Output TRUE if CONF1 can get to CONF2 in at most 2t steps *\
If t=0 then 
        {if (CONF1 = CONF2
         or CONF1 goes to CONF2 in one step on machine N)
         then output TRUE else output FALSE}
For each CONF
  {If CHECK(CONF1,CONF,t-1) and CHECK(CONF,CONF2,t-1) then output TRUE}
Output FALSE

We can implement CHECK by only having to store a constant number of configurations at each level of the recursion with a recursive depth of t for a total space of O(ts(n)).

Let CONF₀ be the initial configuration encoding x. We can now give our main routine.

MAIN
Let r be the smallest integer at least log2(cs(n))
For each CONF in an accepting state
   {If CHECK(CONF0,CONF,r) then output TRUE}
Output FALSE

Total space used: O(log₂(c^s(n))s(n)) = O(s²(n)).