5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Can you please link to your sources? $\endgroup$ – Raphael Jan 17 '14 at 21:42
5
$\begingroup$

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.

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

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.

$\endgroup$
  • 2
    $\begingroup$ 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}$ $\endgroup$ – user12859 Jan 17 '14 at 21:58
  • $\begingroup$ @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. $\endgroup$ – AndrewK Jan 17 '14 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.