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

[Computational Complexity] Favorite Theorems: P = NP for Space

Expand Messages
  • Lance
    June Edition In 1970 Walter Savitch proved one of the truly classic results in complexity showing that one can simulate nondeterministic space in deterministic
    Message 1 of 1 , Jul 12, 2005
    • 0 Attachment
      June Edition

      In 1970 Walter Savitch proved one of the truly classic results in complexity showing that one can simulate nondeterministic space in deterministic space with only a quadratic slowdown.

      Walter Savitch, Relationships Between Nondeterministic and Deterministic Tape Complexities, Journal of Computer and System Sciences, 1970.

      In complexity terms, for any space constructible function s(n) ≥ log n,

      NSPACE(s(n))⊆DSPACE(s2(n))

      You can find the proof in an earlier post.

      As a consequence you get PSPACE=NPSPACE, which is why you don't see NPSPACE in the zoo.

      Chandra, Kozen and Stockmeyer used a modification of the Savitch algorithm to show that polynomial space can be simulated in alternating polynomial time. This relationship led to showing lots of games PSPACE-complete and played a critical role in showing IP=PSPACE.

      Circuit wise, Savitch's algorithm puts NL (nondeterministic log-space) in SAC1 (log-depth circuits with constant fan-in ANDs and unbounded fan-in ORs).

      For a directed graph G=(V,E), let Gk=(V,Ek) where (u,v)∈Ek if there is a path of length at most k from u to v in G. One way to view Savitch's theorem is to compute G2k from Gk using O(log n) additional space. You then apply this graph powering log n times to get from G=G1 to Gn where (u,v)∈En if there is a path from u to v in G.

      Reingold uses a similar paradigm in his result that SL = L. He shows for undirected graphs that you can do a weaker form of graph powering (using expander graphs) but with a similar effect using only O(1) additional space at each step.

      But after 35 years we still have no better upper bound on the deterministic space complexity of NL than O(log2 n) from Savitch's Theorem.

      --
      Posted by Lance to Computational Complexity at 7/12/2005 05:54:00 AM

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