Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Lance Fortnow
    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, 2003
    • 0 Attachment
      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

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.