The problem: you have a number of cities, and you know the distance from each city to every other. A salesman has to construct a route which takes him through every city once and only once. Find the shortest route.

This is an *exponential* problem. It is logically impossible to
construct an algorithm that solves the problem exactly whose computation
time goes up more slowly than the exponential of the number of cities.
There are many problems of this kind, often concerned with packing
objects in a way that minimise the number of gaps. For example,
scheduling advertising slots. See *Emperor's New Mind* by Penrose,
pp 140-146.

Wed Feb 14 23:47:23 GMT 1996