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.

– Raphael
Jan 17 '14 at 21:42

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).

Also see AndrewK's answer regarding the subset symbol, I think this is the issue here.

• 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.$\}$ Jan 17 '14 at 23:49

It's not a dumb question. One thing to note is that not all literature agrees on how exactly to use the different subset symbols. It is entirely plausible that two sources could be using the same symbols to mean different things, thereby communicating the same information! Confusing, isn't it?

Pending review: For an intuitive understanding, think about how non-deterministic TMs theoretically work. They can always accomplish the same tasks in the same memory spaces, and they can often also accomplish the same tasks in smaller memory spaces. This means more spaces are available to a non-deterministic TM. NSPACE contains more than just DSPACE. DSPACE is a proper/strict subset of NSPACE.

• 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. Jan 17 '14 at 22:18