# Is Hamiltonian path NL?

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.

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.