Day 9

We looked at deterministic and nondeterministic space complexity and showed the basic relationships:

DTIME(f(n)) ⊆ NTIME(f(n)) ⊆ DSPACE(f(n)) ⊆ NSPACE(f(n)) ⊆ ∪_c DTIME(c^f(n))

We also proved Savitch's theorem that NSPACE(s(n)) is contained in DSPACE(s²(n)).

Links:

• Relationships between nondeterministic and deterministic tape complexities by Walter Savitch
• My writeups of Space Complexity and Savitch's Theorem