Ron Hilton over at Absolutely No Machete Juggling has an excellent post on the traveling salesman problem. Hilton explains that when people say the traveling salesman problem is NP Complete they are almost always wrong. Almost because there are two formulations of the problem but only one of them is NP Complete and it’s not the formulation that everyone associates with the problem.
You can follow the link for the details but what I found especially interesting in the post was his explanation of the meanings of NP, NP Complete, and NP Hard. It’s one of the best explanations that I’ve seen. The short summary is
| NP | A proposed solution can be verified in polynomial time |
| NP Hard | The problem is as hard or harder than any NP problem |
| NP Complete | The problem is both NP and NP hard |
but be sure to read Hilton’s more complete explanation. He also has a nice Venn diagram that shows how the three properties relate to each other.
You often see problems described as NP or NP Complete so if you have any doubt as to what that means, spend a couple of minutes on this post. It will be worth your while.