Savitch's Theorem

From dankwiki
Revision as of 10:32, 8 November 2012 by Dank (talk | contribs) (Created page with "f(n) ≥ log(n) implies that NSPACE(f(n)) ⊆ DSPACE(f(n)²), thus * PSPACE = NSPACE * NL ⊆ L² CATEGORY: Computer Science Eponyms")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

f(n) ≥ log(n) implies that NSPACE(f(n)) ⊆ DSPACE(f(n)²), thus

  • PSPACE = NSPACE
  • NL ⊆ L²
Retrieved from "https://nick-black.com/dankwiki/index.php?title=Savitch%27s_Theorem&oldid=5178"