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-completenessIt'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. ;-)

> and it is widely believed that no

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

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.

ReplyDelete