Suppose I nondeterministically walk around in a graph with n vertices.

When looking for a Hamiltonian path, at some point I’ve walked n/2 vertices.

There are (n choose n/2) different combinations of vertices I could have walked (meaning the unordered set, not the ordered walk).

Each of those states must be distinct from one another.

If not, then, depending on the remaining n/2 vertices, I would decide the wrong answer.

Therefore, midway through the path, at n/2, I need (n choose n/2) different states. That is too big for logspace.

Therefore you cannot decide a Hamiltonian path by nondeterministically walking around.

Does this imply Hamiltonian path cannot be decided in nondeterministic logspace - at least by "walking around"?

  • 1
    $\begingroup$ You show that one approach doesn’t work. Others might. The difficulty in proving lower bound is ruling out all possible approaches. $\endgroup$ – Yuval Filmus May 6 '20 at 21:27
  • $\begingroup$ I asked a different logspace question. cs.stackexchange.com/questions/125307/… I understood "no, cannot be done in logspace." I'm uncertain. I was only given a hint. However, if that problem cannot be done in logspace for the given reason, then I think a similar argument could apply to Hamiltonian Path. $\endgroup$ – Jesus is Lord May 7 '20 at 17:28
  • $\begingroup$ @YuvalFilmus Makes sense, you're saying: "There exists an approach that I haven't ruled out." $\endgroup$ – Jesus is Lord May 7 '20 at 17:34
  • $\begingroup$ When people say "cannot be done in logspace", what they really mean is "we don't think it can be done in logspace". Beyond the space hierarchy theorem, we don't have any techniques to prove that a problem cannot be solved in logarithmic space. $\endgroup$ – Yuval Filmus May 7 '20 at 18:21
  • $\begingroup$ @Yuval Filmus Is my understanding correct? The space hierarchy theorem says "nondeterministic space can be done in at most the square of the deterministic space." Have we proved "nondeterministic space is at least the square of deterministic space?" Have we proved a lower-bound on space? $\endgroup$ – Jesus is Lord May 7 '20 at 18:38

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.