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^{2}(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 =
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(CONF_{1},CONF_{2},t) \* Output TRUE if CONF_{1}can get to CONF_{2}in at most 2^{t}steps *\ If t=0 then {if (CONF_{1}= CONF_{2}or CONF_{1}goes to CONF_{2}in one step on machine N) then output TRUE else output FALSE} For each CONF {If CHECK(CONF_{1},CONF,t-1) and CHECK(CONF,CONF_{2},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_{0} be the initial configuration encoding x. We can
now give our main routine.

MAIN Let r be the smallest integer at least log_{2}(c^{s(n)}) For each CONF in an accepting state {If CHECK(CONF_{0},CONF,r) then output TRUE} Output FALSE

Total space used: O(log_{2}(c^{s(n)})s(n)) =
O(s^{2}(n)).

## No comments:

## Post a Comment