[Solved]: Is DSPACE properly contained in NSPACE?

Problem Detail: 

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.

Asked By : NumberFour

Answered By : sdcvvc

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19794

 Ask a Question

 Download Related Notes/Documents