0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ I don’t understand your reasoning. Given an NL machine, how do you construct an equivalent L machine? $\endgroup$ – Yuval Filmus Nov 3 '19 at 22:23
  • $\begingroup$ 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? $\endgroup$ – Olivier Melançon Nov 3 '19 at 22:32

Your Answer

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

Browse other questions tagged or ask your own question.