The life of the travelling salesman isn't easy. Every day brings the indignity of slammed doors, cheap hotels and appalling roadside diners. No wonder travelling salesmen need company cars.
Help is at now at hand.
Computer scientists Scott Kirkpatrick at IBM's T. J. Watson Research Centre in New York State and colleagues show how, even if the problem remains hard to solve, it might at least be possible to distinguish the merely difficult from the mind-bogglingly intractable. Their study, published in the 8 July issue of Nature , could help to guide the design of new methods for solving such thorny computer problems. In the worst of these, the amount of computer power needed to solve the problem grows exponentially with the size of the problem. Take the case of the hapless travelling salesman. His aim is to visit a certain number of towns, taking the shortest possible route, so that he can be home before his dinner shrivels in the oven.