TRAVELING SALESMAN   TSP.

Given a list of cities and a table containing the distances between cities (all pairs) and a number n, is there a way to visit all the cities exactly once and return to the starting city with total distance not exceeding n?

There are two parts to proving a problem NP-Complete.

1.  We have to prove that the problem is in NP.

In this case, yes.  If we envision a NTM as an infinitely parallel machine, we can have the processors try every single possible path returning to its starting point.  Each processor will add up the total distance traveled and will return YES if that value is <= n.  This is clearly polynomial time.  (It's Th(n) time to look up and add up all those numbers.)  If any processor return YES, the answer is YES, it can be done.

2.  We reduce a KNOWN NP-Complete problem to the problem we're trying to prove.  In this case, we will use Hamiltonian Cycle:  Given a graph G=(V,E), is there a cycle that visits every node exactly once?

So, can we in polynomial time transform valid input from HC to valid input for TSP?

For each vertex in V in HP, we make a city in TSP.  (It doesn't matter what we call the city:  "City 1" "City 2" whatever.)  If there is an edge between two nodes in G in HP, we will set the distance between corresponding cities to be 1.  If there is no edge in the graph between those vertices, the distance in TSP between the corresponding cities will be |V|+1 (one more than the number of vertices).  And we will set our n in TSP to be equal to the total number of vertices in V (or the total number of cities).

Do the inputs yield the same output?

YES ==> YES

Assume HC gives a YES answer.  That means the graph contains a Hamiltonian Cycle, a cycle that visits every node exactly once.  Well, my traveling salesman can then visit the cities in the exact same order.  The distance between successive cities will always be one because the salesman is always following the same path as the Hamiltonian Cycle (which will have edges between successive nodes in the cycle).  Since there are n cities and I always travel of 1 to get between cities, I travel a total distance of n.  Since n <= n, the Traveling Salesman can do it, so TSP gives an answer of YES.

YES <== YES

Assume TSP gives a YES answer.  That must mean that the salesman can visit all cities and return to the starting point with a total distance <= n.  Ergo, the salesman must not be traveling along any of those paths of length n+1.  So the salesman must be traveling between cities with a distance of 1.  Thus the corresponding nodes in HC have edges between them.  So, since there is a path in HC that visits every node and returns to its starting point, HC also gives an answer of YES.

Once again note that we never attempt to actually solve TSP or HC.  We just transform the input from one to the other.  Also note that we have not generated all possible input for TSP...but we don't have to.  We need to transform every possible input to HC, but we don't need to cover all possible inputs for TSP.