## 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) :

> 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.