For NP-complete you need a slight modification of the traveling salesman problem. An example would be that you need to visit 5 cities, but you need to travel less than 50 miles. Is there a route that will get you through all 5 cities in less than 50 miles?
To find a solution need to search through all the permutations (factorial time), but to verify that you have a solution is polynomial time.
However, your original traveling salesman problem is NP-hard because there is no way to verify that you have the shortest route without calculating all of the routes.
I probably have an advantage here because read the Sipser book less than a year ago. Let's see what I remember in another three years.