Previous Lesson |
Next Lesson
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 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)).
