Two recent blog ,posts discussing the Traveling Saleman Problem (TSP) led me to write this post.  The two blog posts are What is Operations Research by Graham Kendall, and I’ve Been Everywhere (Optimally…)   by Rob Jefferson. Both are worth reading (I wish I had written them..).  These posts share two interesting properties:  both discuss the TSP, and both make a mistake about the TSP.  The same mistake occurs regularly in blog posts and even books. 

The mistake is to say that the TSP is NP complete.

This is wrong.  Truth is that TSP is NP hard.

...