"Meanwhile, the Clay Mathematics Institute is offering a $1 million prize to anyone who can show whether the Traveling Salesman Problem can be fully solved at all, which the mathematician Jordan Ellenberg recently called “the biggest open problem in complexity theory.”
See what can be found in the Theatre Section of the New York Times? And you thought it was for egg-head liberals.
I suspect that the article may have oversimplified what is needed to win the prize, unless the Clay Institute is currently offering TWO one million dollar prizes. But that’s the NYT for you.
The diagram obviously shows a solution (not necessarily the best solution) to a problem different from the one that was a recent Car Talk Puzzler. The only point in New England appears to be Boston, which means at least four states aren’t on the route in that part of the country. It also misses both Nevada and New Mexico entirely, and has two points in California. (That’s just the parts of the country I can speak for without seeing state lines on the map.)
The diagram shows a solution for an optimal tour through 33 cities in a 1962 Procter and Gamble contest. Yes, it is optimal.
If you did not read the article, you should not criticize.
If one is interested, one could listen in to the MIT open courseware classes which are filmed MIT undergraduate classes. (It’s a bit hokey, as you will see for yourself if you watch, but it is interesting if one has the time and curiosity.) A discussion of optimization problems in general and the 0/1 Knapsack problem in particular starts at
If you want someone to read the article before commenting on the difference between the graphic you posted and the recent Car Talk Puzzler, you shouldn’t have posted the graphic. If you think that was criticism, your definition of criticism is overbroad.
I forget the exact wording, but didn’t the solution to the travelling salesman puzzler offered up on the radio show require identifying a state which is only connected to one other state? I think Maine connects only to New Hampshire. All other states (contiguous) connect to at least two other states. Florida for example connects to both Georgia, and Alabama.
Way to go @George_San_Jose1
You revived a 10 year old thread.
'tain’t an easy task , that’s for sure … 
OK. as long as the dead have been resurrected, nice math problem but very unrealistic. I always get a charge out of these stories to simply mask a math exercise for those that like to work out math problems. At any rate it’s all academic because that’s not the way a traveling salesman would have to do it, unless all he/she/it was doing is cold calls. Then why drive all over the country doing that? You would tend to go into an area and work that area but would be going back and forth etc. depending on appointments and call backs. Of course now like with the yellow pages, you would do your driving with your fingers and computers.
This is the famous NP-Complete problem, useful in many ways List of NP-complete problems - Wikipedia , the ‘traveling salesman’ is a trivial example meant to make it seem familiar to a broad audience. Solving it is worth far more than a billion dollars. People have already spent millions trying to solve it - this prize won’t recruit any competent entrants.