Sorry, an error occurred while loading the content.

## [My Computational Complexity Web Log] Foundations of Complexity Lesson 18: Savitch's Theorem

Expand Messages
• Previous Lesson Unlike what we believe for time, there is a polynomial relation between deterministic and nondeterministic space. Savitch s Theorem (1970):
Message 1 of 1 , May 14 1:31 PM
Previous Lesson

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

Savitch's Theorem (1970): NSPACE(s(n))⊆DSPACE(s2(n))

Proof: Recall the definition of tableau (as described in Lesson 12). 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)).

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 5/14/2003 4:30:51 PM