Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I have read of an algorithm that a non-deterministic Turing machine $N$ can run to determine whether a given graph $G$ has a Hamiltonian path from the start node $s$ to a certain node $n$:

  1. Write a list of $x$ numbers $p_1, p_2, p_3 ... p_x$, where $x$ is the number of nodes in $G$. Each number in this list is non-deterministically selected to be from 1 to $x$.

  2. Check for repetitions in this list. If a repetition exists, reject.

  3. Check whether both $s = p_1$ and $n = p_x$. If either do not hold, reject.

  4. For each $i \in [1, x - 1]$, check whether $(p_i, p_{i + 1})$ is an edge of $G$. If any are not, reject.

  5. Accept.

I do not understand how this algorithm works. Specifically, in step 1, why am I making a list of random (potentially repeating) numbers from 1 to $x$ (What does this list have to do with the nodes of $G$?)?

Likewise, in step 4, why does $(p_i, p_{i + 1})$ represent a potential edge in $G$?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

There's a couple of bits of information that are key to making this make sense:

  1. Each $p_{i}$ should be a label for a vertex in $G$. Typically $p_{i} \in [1,x]$, but it's not compulsory that you have to label the vertices from 1 to $x$. So the first step is effectively producing a putative list of vertices that could be a path. The rest just checks that it is actually a path (a hence why $(p_{i},p_{i+1})$ could be an edge).

  2. The list is not random. It is selected non-deterministically. This is most definitely not the same as randomly selected. Non-determinism is a special theoretical property where a non-deterministic machine can "guess" a correct answer if it exists, however correct also has a special meaning, in that it selects an answer that will lead to an accepting state if such an answer exists. This may not be the right answer, just one that will make the Turing Machine say Yes - so we still have to check it.

So the algorithm guesses really cleverly a list (in fact an ordering) of all the vertices of the graph, and then checks that it actually makes a Hamiltonian Path from $s$ to $n$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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