Not long ago, a team of researchers from Stanford and McGill universities broke a 35-year record in computer science by an almost imperceptible margin — four hundredths of a trillionth of a trillionth of a trillionth of a trillionth of a percent, to be exact. The advance — made to that poster child for hard-to-solve computer science quandaries, the “traveling salesman” problem — was too minuscule to have any immediate practical significance, but it has breathed new life into the search for improved approximate solutions.
*Original story reprinted with permission from Simons Science News, an editorially independent division of SimonsFoundation.org whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the computational, physical and life sciences.*The traveling salesman problem asks: Given a collection of cities connected by highways, what is the shortest route that visits every city and returns to the starting place? The answer has practical applications to processes such as drilling holes in circuit boards, scheduling tasks on a computer and ordering features of a genome.
The traveling salesman problem is easy to state, and — in theory at least — it can be easily solved by checking every round-trip route to find the shortest one. The trouble with this brute force approach is that as the number of cities grows, the corresponding number of round-trips to check quickly outstrips the capabilities of the fastest computers. With 10 cities, there are more than 300,000 different round-trips__.__ With 15 cities, the number of possibilities balloons to more than 87 billion.
In the early days of computers, mathematicians hoped that someone would come up with a much better approach to large traveling salesman problems — some algorithm that would allow computers to solve them in a reasonable amount of time. But while computer scientists have made progress with specific scenarios — identifying the shortest round-trip route for__ a 49-city map in the 1950s, a 2,392-city map in the 1980s and a 85,900-city map in 2006 — no one has devised an algorithm that can efficiently solve every traveling salesman problem. According to a landmark paper published in 1972, such a solution might not even be possible. Computer scientist Richard Karp, of the University of California at Berkeley, __showed that the traveling salesman problem is “NP-hard,” which means that it has no efficient algorithm (unless a famous conjecture called P=NP is true — but the majority of computer scientists now suspect that it is false).