Given graph G and vertices v and w can you non-deterministically walk the "least Hamiltonian path" from v to w, if it exists?

Question

My understanding of non-deterministic algorithms is that they're "as lucky as you want".

...you can think of the algorithm as being able to make a guess at any point it wants, and a space alien magically guarantees it will always make the right/lucky guess.

For example, if you choose two vertices v and w, if there's a vw path, then you can non-deterministically walk a vw path, luckily correctly guessing the vertices to walk in a vw path. Given this is true of paths in general, I wonder if the same can be done for Hamiltonian paths. I would think so, but I'm not sure.

Therefore, my first question is: if you can non-deterministically walk a vw path, can you non-deterministically walk a Hamiltonian path from v to w, if a Hamiltonian path exists? If you can non-deterministically walk a Hamiltonian path, I wonder if the same can be done for an additional constraint, what I'm calling a "least Hamiltonian path." I would think so, but I'm not sure.

Define the least Hamiltonian path from v to w to be the Hamiltonian path such that the second vertex is the smallest it can be, then the third vertex is the smallest it can be, the fourth is the smallest, etc. Assume vertices are integers. For example, if we consider K5 the graph with vertices {1,2,3,4,5} and all possible edges, then the least Hamiltonian path for (v,w) = (2,3) is 21453. If you were at vertex 2, the next least vertex would be 1. Then, the next least vertex would 4. etc.

Therefore, my actual question is: Given graph G and vertices v and w can you non-deterministically walk the least Hamiltonian path from v to w, if it exists?

Motivation: If so, then perhaps there's a space-efficient algorithm for non-deterministically walking a Hamiltonian path: You can keep a counter for vertices v and w, and go through each pair of vertices such that v<w, checking for the existence of a least Hamiltonian path. To ensure all vertices in G are reached, keep a counter for the number of vertices walked (this should equal N if there are N vertices). Also, ensure that each vertex in the path is unique. The least Hamiltonian path from v to w will be unique, therefore it can be walked multiple times (each time you walk through it, starting at v, you'll non-deterministically guess the next least vertex in the least Hamiltonian path). You could use two counters to ensure no vertices are repeated - one for the vertex you're checking to see if it's unique (loop through the vertices in the least Hamiltonian path), and another counter for a second pass through the least Hamiltonian path. Ensure the second counter encounters the value of the first counter exactly once (use a boolean flag to keep track of this).

Answer 1

No. There has to be a way to verify that your choices led to a correct choice, in polynomial time (with an ordinary deterministic computer). Given a particular Hamiltonian path, there's no way to verify it is the least Hamiltonian path (in polynomial time).

The "space alien" stuff is just intuition, but if you want to know what it means in a precise way, you need to go to the formal mathematical definition. My favorite definition of NP is the verifier-based definition. With that definition, there is no obvious way to pick a short certificate that a polynomial-time (deterministic) algorithm can use to verify that a proposed solution to the problem is correct.