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
