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(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)).