I'm studying Sipser's book Introduction to the Theory of Computation. In Time Complexity chapter the following NTM is given as a solution to HAMPATH problem (Hamiltonian Path http://en.wikipedia.org/wiki/Hamiltonian_path):
--------
N = On input <G,s,t> where G is a directed graph with nodes s (starting node) and t (destination node):
1. Write a list of m numbers P1, ..., Pm where m is the number of nodes in G. Each number in the list is nondeterministically selected to be between 1 and m.
2. Check for repetitions in the list. If any are found reject
3. Check whether s = P1 and t = Pm. If either fail, reject
4. For each i between 1 and m-1, check whether (Pi, Pi+1) is an edge of G. If any are not, reject. Otherwise, all tests have been passed so accept
--------
Now my problem; let's say G has 5 nodes, so in the step 1 a list of numbers is written from 1 to 5.
In step 2, we are checking for repetitions, how can we possibly have repetitions when we are writing each number once? As I can understand it when we write the numbers from 1 to m, we will never have reptitions, each number is written once and then we are moving on to write the next number.
I'm guessing that somewhere we are choosing a random path and we are testing it. But I can't see it in the algorithm, it's not in the input( <G,s,t> ), it's not in the algorithm's steps. We are just writing a list of numbers from 1 to m.
Now I know that most probably I've misundestood the above algorithm, I'm not saying Sipser is wrong :P but where is the list that might contain a "repitition"? I can't see it.
Any ideas? :)