2
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks for the answer! Are you saying: “Your nondeterministic algorithm implies the existence of a deterministic algorithm, which we don’t have an obvious algorithm therefore the nondeterministic algorithm is wrong”? I don’t follow that. It’s easy to come up with a nondeterministic logspace algorithm for graph connectivity: take a random walk. However a deterministic logspace algorithm for undirected connectivity appears to be more complicated. What if the deterministic polynomial time algorithm is complicated? $\endgroup$ Apr 17 at 20:52
  • $\begingroup$ @JesusisLord, no, that's not what what I'm saying. One way to view nondeterministic computation is that if there is any computation path (any sequence of nondeterministic choices) that leads to an accepting state, then the nondeterministic chooser will select some such sequence of choices. For this to be useful to you, you need a way to recognize (in deterministic polynomial time) whether to "accept", i.e., whether a particular sequence of choices will give you a least Hamiltonian path. There's no obvious way to do that. $\endgroup$
    – D.W.
    Apr 17 at 21:27
  • $\begingroup$ If this doesn't make sense, I recommend working through the formal mathematical defenses. English text and analogies (space aliens etc.) are an informal/imprecise attempt at summarizing the concepts, but it can sometimes be misleading. I know the answer and am trying to help give you some intuition for that answer while avoiding math formalisms, but that might not be possible. Ultimately the mathematical definitions are the authoritative way to resolve this. You can find definitions of NP, etc., in standard textbooks. $\endgroup$
    – D.W.
    Apr 17 at 21:29
  • $\begingroup$ @DW Thank you! Yes, makes sense. $\endgroup$ Apr 17 at 22:35

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.