Given graph G and vertices v and w can you non-deterministically walk the "least Hamiltonian path" from v to w, if it exists?
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 &quot;space alien&quot; 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.