1
$\begingroup$

NL is what can be solved by a non-deterministic Turing machine in logspace.

Could you non-deterministically "guess" the correct Hamiltonian path in logspace, keeping track of the current vertex (log(n) bits) and a count of how many vertices you've visited (log(n) bits)?

Does that mean finding a Hamiltonian path is NL?

(This is too simple; what is my mistake?)

A Hamiltonian path is a path that visits all vertices in a graph. The concept exists for directed and undirected graphs.

$\endgroup$
1
$\begingroup$

This describes a non-deterministic walk, not a path.

You may end up counting the same vertex more than once.

Given a start configuration of (v, 0) (meaning you're at vertex v and you've traversed 0 edges), when you're at configuration (w, n-1) (meaning now you're at vertex w and you've traversed n-1 edges), all you know is that you have a v->w walk of length n-1.

If there's a Hamiltonian path, you will find it non-deterministically, however, you will not "know" that you've found it by examining the (w, n-1) state.

This algorithm decides walks of length n-1.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.