## Friday, February 01, 2008 ... / / ### Dog solves the travelling salesman problem

The travelling salesman problem is classified as NP-hard and it is one of the most notorious problems in the class.

The task is to find the cheapest closed path connecting n=74 balloons, with well-defined costs for the transfer between any two pairs of balloons, and exact your revenge on them. (The tasks where the balloons explode and where they don't are equivalent.)

See P vs NP and NP-completeness
It's not easy because the solution space is 1/2 (n-1)! = 1/2 times 73! and it is widely believed that no algorithm that would only take time proportional to a power of n=74 can exist.

However a dog called Prof Simon, not to be confused with Jim Simons, has solved the problem for n=74 in t=47 seconds. Congratulations. ;-)    #### snail feedback (2) :

reader Frank Ch. Eigler said...

> and it is widely believed that no
> algorithm that would only take time
> proportional to a power of n=74 can exist.

That's not right. The issue is scaling
of the computation time as the number
increases, not the speed of computation
for any particular number.

reader Luboš Motl said...

Jesus Christ, I am not silly. But let me assure you that 74 is a large enough number in this context and the actual required time for n=74 will almost exactly match the asymptotic expectation with n=74 substituted.

(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){ (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o), m=s.getElementsByTagName(o);a.async=1;a.src=g;m.parentNode.insertBefore(a,m) })(window,document,'script','//www.google-analytics.com/analytics.js','ga'); ga('create', 'UA-1828728-1', 'auto'); ga('send', 'pageview');