Complexity & Chaos 167
TRY THE PUZZLE ON THE WEB Warning: Don’t spend too long on these problems.
The reason I warned you not to spend too long is that solving the 50-city problem would take longer than the age of the known universe. NP problems get harder very fast as the number of elements goes up. A 50-city problem is hugely larger than a five-city problem, not just ten times harder.
The Clay Mathematics Institute has offered a $1 million prize for anyone who can say whether NP problems are really as hard as they appear. It may be there is a general trick or a series of tricks that allow you to solve any NP problem in a shorter time. If you could do this, the problem would be demoted to P, allowing fast computers to tackle it. No one has yet found a proof of the P=NP problem. At the time of writing several proofs are sitting with the Clay Prize judges but don’t hold your breath. Most people assume there is no solution. If you want to have a crack at the problem let me state it in simple terms.
Marplent
bo
rr
H
H o
Traveling Salesman
LS lac oo
HOUSE_OVERSIGHT_015857