# Why is $DSPACE(\log(n)) = NSPACE(\log(n))$ not known?

Here $$DSPACE(\log(n))$$ is the family of algorithms for which there exists a deterministic Turing machine using $$O(\log(n))$$ space.

On the other hand $$NSPACE(\log(n))$$ is the family of algorithms for which there exists a non-deterministic machine using $$O(\log(n))$$ on all the possible path it could explore.

I understand that $$DSPACE(\log(n)) \subset NSPACE(\log(n))$$ because a Turing machine is just a special case of a non-deterministic one. Although, it seems to be that the fact $$NSPACE$$ considers all the possible path of a non-deterministic machine makes it a way stronger condition which would lead to $$NSPACE(\log(n)) \subset DSPACE(\log(n))$$.

Although, to the best of my knowledge $$L = NL$$ is an open problem which I surely did not crack just there.

Why is my reasonning wrong and what would be a good counterexample?

• I don’t understand your reasoning. Given an NL machine, how do you construct an equivalent L machine? – Yuval Filmus Nov 3 '19 at 22:23
• My reasonning is clearly incomplete and just writing the question is slowly briging me some insight. My intuition was that if I have an NL machine such that each path uses O(log(n)) space, then it must be that the problem is simple enough to use O(log(n)) space deterministically. I think I see that using the NL machine to go through all paths is not feasible since you have to count the path and there are exponentially many, which requires a O(n) sized counter. Up to that point, is that correct? – Olivier Melançon Nov 3 '19 at 22:32