# Savitch's Theorem

From dankwiki

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

- PSPACE = NSPACE
- NL ⊆ L²

From dankwiki

Revision as of 15: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²

- modified on 8 November 2012 at 15:32.
- copyright © 2008–2023 nick black. all rights worth shit.