Calculating the quickest route for a salesman to travel between several cities is one of the hardest tasks in mathematics today. Most scientists believe that this is a 'non-deterministic polynomial-time' problem, otherwise known as an 'NP-complete' problem. In the worst cases the amount of computer time needed to solve an NP-complete problem grows exponentially with the size of the problem. In other cases, however, the computer time needed grows much slower, as some power of the system size. Now Scott Kirkpatrick of the IBM Thomas J. Watson Research Centre in the US, and colleagues in France, Israel and Italy have now found a way to distinguish between these exponential and polynomial cases (Nature 400 133).
Kirkpatrick and co-workers found that the computer algorithms used to solve NP-complete problems can undergo sudden phase transitions as the various criteria used to search for a solution are varied. The solutions get harder to find at the onset of the phase transition – as the search ‘freezes’ – and then easier again once the system has passed through the phase transition. The team noticed that if the phase transition is abrupt, like the freezing phase transition, the problem is exponentially hard. However, if the transition is continuous, like the demagnetization of iron when heated, then the problem is only polynomially hard.
