# Is DSPACE properly contained in NSPACE?

It may be a dumb question, but is $\mathsf{DSPACE}(f(n)) \subset \mathsf{NSPACE}(f(n))$ or is $\mathsf{DSPACE}(f(n)) \subseteq \mathsf{NSPACE}(f(n))$? In other words, is the containment relation proper or not? Wikipedia says the first one, while the ComplexityZoo says the other one.

It's open whether $\mathsf{DSPACE}(\log n) = \mathsf{NSPACE}(\log n)$, which is the $\mathsf{L}=\mathsf{NL}$ question. As far as I know, the closest thing we can say are theorems by Savitch $\mathsf{NSPACE}(f(n)) \subseteq \mathsf{DSPACE}(f(n)^2)$ and Immerman–Szelepcsényi's ($\mathsf{NSPACE}$ is closed under complement).
• There we go! The jump to L vs. NL is a short one too. For reference: $DSPACE(f(n)) = \{L|L$ can be decided by a deterministic TM in $O(f(n))$ space.$\}$ $NSPACE(f(n)) = \{L|L$ can be decided by a non-deterministic TM in $O(f(n))$ space.$\}$ – AndrewK Jan 17 '14 at 23:49
• Do you know a proof that DSPACE is a proper/strict subset of NSPACE? $\:$ (That is a stronger statement than "The set of DSPACE machines is a proper/strict subset of the set of NSPACE machines.".) $\hspace{1.15 in}$ – user12859 Jan 17 '14 at 21:58
• @RickyDemer You know, I've been looking for that myself. Intuitively it makes sense, Wikipedia claims it's true, but where's the proof? There's a reference to Savitch's theorem, but that's for $NSPACE(f(n))\subseteq DSPACE((F(n))^2)$. I'm going to strike it out for now. – AndrewK Jan 17 '14 at 22:18