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. | inne Cre | | al | | | | | | | | 4 2. oo ‘ | [a | f * aA I" oe ie | © y | Traveling Salesman HOUSE_OVERSIGHT_015857