# $1M Prize for Solution of Traveling Salesman Problem **URL:** \ **Category:** The Show\ **Created:** [March 17, 2012, 8:44am UTC](https://community.cartalk.com/t/1m-prize-for-solution-of-traveling-salesman-problem/71469 "2012-03-17T08:44:44Z")\ **Posts on this page:** 10\ **Page:** 1
**Author:** ![Mechaniker](https://avatars.discourse-cdn.com/v4/letter/m/13edae/32.png) [@Mechaniker](https://community.cartalk.com/u/Mechaniker)\ **Post date:** [March 17, 2012, 8:44am UTC](https://community.cartalk.com/t/1m-prize-for-solution-of-traveling-salesman-problem/71469/1 "2012-03-17T08:44:44Z")
![](https://global.discourse-cdn.com/cartalk/original/3X/e/d/ed69dc48027aaeb6826d9d2cd5119f6dbac025a5.jpeg) > _"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.”_ > > [NYT: March 14 - The Traveling Salesman Problem](http://www.nytimes.com/interactive/2012/03/01/theater/201203-death-of-a-salesman-interactive.html?scp=1&sq=traveling%20salesman%20problem&st=cse) See what can be found in the Theatre Section of the New York Times? And you thought it was for egg-head liberals. ---
**Author:** ![littlemouse](https://avatars.discourse-cdn.com/v4/letter/l/c4cdca/32.png) [@littlemouse](https://community.cartalk.com/u/littlemouse)\ **Post date:** [March 17, 2012, 2:35pm UTC](https://community.cartalk.com/t/1m-prize-for-solution-of-traveling-salesman-problem/71469/2 "2012-03-17T14:35:11Z")
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. ---
**Author:** ![dadoctah](https://avatars.discourse-cdn.com/v4/letter/d/ee59a6/32.png) [@dadoctah](https://community.cartalk.com/u/dadoctah)\ **Post date:** [March 18, 2012, 3:22am UTC](https://community.cartalk.com/t/1m-prize-for-solution-of-traveling-salesman-problem/71469/3 "2012-03-18T03:22:32Z")
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.) ---
**Author:** ![Mechaniker](https://avatars.discourse-cdn.com/v4/letter/m/13edae/32.png) [@Mechaniker](https://community.cartalk.com/u/Mechaniker)\ **Post date:** [March 18, 2012, 4:49pm UTC](https://community.cartalk.com/t/1m-prize-for-solution-of-traveling-salesman-problem/71469/4 "2012-03-18T16:49:39Z")
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. * * * BTW, companies like MapQuest calculate and store in data bases the shortest distances between thousands of US cities. In that way they have converted a problem like the TSP which requires exponentially increasing computer time as the number of cities increases into a problem which increases in polynomial fashion with number of cities. The secret to all clever optimization problems is to avoid recomputing and to store data on the fly to be used later. 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 > **[Online College Courses & Accredited Degree Programs | 2018](http://academicearth.org/online-college-courses/)** > > Hundreds of online college courses from the nation's best schools. No fees, no commitment -- learn on the go with lectures and interactive courses. ---
**Author:** ![littlemouse](https://avatars.discourse-cdn.com/v4/letter/l/c4cdca/32.png) [@littlemouse](https://community.cartalk.com/u/littlemouse)\ **Post date:** [March 19, 2012, 1:07am UTC](https://community.cartalk.com/t/1m-prize-for-solution-of-traveling-salesman-problem/71469/5 "2012-03-19T01:07:32Z")
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. ---
**Author:** ![George\_San\_Jose1](https://avatars.discourse-cdn.com/v4/letter/g/e5b9ba/32.png) [@George\_San\_Jose1](https://community.cartalk.com/u/George_San_Jose1)\ **Post date:** [September 17, 2021, 11:22pm UTC](https://community.cartalk.com/t/1m-prize-for-solution-of-traveling-salesman-problem/71469/7 "2021-09-17T23:22:41Z")
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. ---
**Author:** ![It\_s-Me](https://sea1.discourse-cdn.com/cartalk/user_avatar/community.cartalk.com/it_s-me/32/12660_2.png) [@It\_s-Me](https://community.cartalk.com/u/It_s-Me)\ **Post date:** [September 18, 2021, 12:35pm UTC](https://community.cartalk.com/t/1m-prize-for-solution-of-traveling-salesman-problem/71469/8 "2021-09-18T12:35:48Z")
Way to go @George_San_Jose1 You revived a 10 year old thread. ---
**Author:** ![George\_San\_Jose1](https://avatars.discourse-cdn.com/v4/letter/g/e5b9ba/32.png) [@George\_San\_Jose1](https://community.cartalk.com/u/George_San_Jose1)\ **Post date:** [September 18, 2021, 10:38pm UTC](https://community.cartalk.com/t/1m-prize-for-solution-of-traveling-salesman-problem/71469/9 "2021-09-18T22:38:16Z")
'tain’t an easy task , that’s for sure … 😉 ---
**Author:** ![bing](https://sea1.discourse-cdn.com/cartalk/user_avatar/community.cartalk.com/bing/32/4619_2.png) [@bing](https://community.cartalk.com/u/bing)\ **Post date:** [September 19, 2021, 5:17pm UTC](https://community.cartalk.com/t/1m-prize-for-solution-of-traveling-salesman-problem/71469/10 "2021-09-19T17:17:12Z")
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. ---
**Author:** ![RandomTroll](https://sea1.discourse-cdn.com/cartalk/user_avatar/community.cartalk.com/randomtroll/32/12184_2.png) [@RandomTroll](https://community.cartalk.com/u/RandomTroll)\ **Post date:** [September 20, 2021, 1:29am UTC](https://community.cartalk.com/t/1m-prize-for-solution-of-traveling-salesman-problem/71469/11 "2021-09-20T01:29:54Z")
This is the famous _NP-Complete_ problem, useful in many ways [List of NP-complete problems - Wikipedia](https://en.wikipedia.org/wiki/List_of_NP-complete_problems) , 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.