## Wednesday, 12 June 2013

### 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(s2(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 = cs(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 2t 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 CONF0 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(log2(cs(n))s(n)) = O(s2(n)).