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