Just Keep Going

A question that has stumped mathematicians for more than a century is the so-called traveling salesman problem: What is the shortest path through a number of points that touches each point once and ends at the starting point? It sounds simple, but as the number of points grows, the number of possibilities grows even faster, outwitting the fastest computers. If there were 25 cities to be visited (points) and a computer calculated a million paths a second and compared them, it would take several billion years to be sure it had the right the answer.

Increasing the number of points makes the problem harder still. What is the shortest path that would allow a salesman to visit each of the capitals of the 48 contiguous states and wind up where he started? Until recently, no one knew. But at the request of Discover magazine, Shen Lin, a mathematician at Bell Laboratories, tackled the problem and solved it. The shortest route covers 10,628 miles, he says. He is offering $100 to anyone who can find a shorter one, but he has proved that there is none.

The problem has many practical applications. In business, as Bell Labs points out, “ ‘shortest path’ may really mean the least hookup wire, travel time or transmission power.” Lin worked out an approach to the problem several years ago that in most cases does not give an absolute solution but a very, very good guess. The computer can skip almost all the arithmetic. The 48 capital problem was solved in less than a second. It has special characteristics that enabled the answer to be known for certain.

But what does it mean in mathematics to say that you think you have the right answer but can’t be sure? This is a new category of mathematical solutions, one created by computers. Purists shudder. A proof that isn’t certain, they say, is no proof at all. Still, for practical purposes, the answer is correct. “If you increase the size of the problem from 48 cities to 1,000 cities,” Lin told us, “no one can show in reasonable time that the solution is optimal. It’s so funny that you know it but you can’t prove it.”

In this respect, mathematics is becoming more like everything else.