Complex computational problems may undergo 'phase transitions,' moving abruptly from difficult to impossible to solve. That's the finding of a group of statistical physicists that includes ICTP research scientist Riccardo Zecchina.

When a Little Means a Lot

Computers are marvellous computational machines that have expanded our ability to analyse and solve 'number' problems that were once beyond our reach. Yet, even the most advanced computers are limited in their computational capabilities. In fact, ever since the dawn of the computer age, mathematicians and computer scientists have examined computational problems in relation to the time and memory resources that are available for their solution.

The issue, more simply stated, is how complex are complex computational problems, and at what point do the variables involved overwhelm the time and resources at hand, making a solution difficult, if not impossible, to compute. Scientists have placed such problems in a special category of analysis, which they have labelled 'nondeterministic polynomial time' (or 'NP-complete') problems.

Take the case of the 'travelling salesperson.' When a salesperson plans to visit three clients in a single business trip, devising the most efficient itinerary is a simple task. If the trip calls for five stops, devising the most efficient route becomes more difficult. And if it's a journey with 12 stops, more difficult still. Say you're a company with 200 travelling salespersons, each of whom is on the road an average of 150 days a year. Is it possible to devise a collective itinerary that provides the shortest route between these multiple destinations? At what point do the variables become too numerous for the problem to be solved?

Until recently, mathematicians and computer scientists have held court over so-called NP-complete problems. Now, a growing cadre of physicists skilled in statistics have entered the problem-solving fray drawing inspiration from both their knowledge of complex systems and the behaviour of materials during phase transitions from gases to liquids and liquids to solids.

In a recent article in Nature, which was subsequently discussed at length in The New York Times, my colleagues and I sought to shed new light on NP-complete problems in ways that would help other researchers-in computer science, mathematics and physics-understand the nature of multivariable computational problems.

Here's our conclusion: Such problems may not become increasingly complex with each new variable and condition, but instead may cross a solvable/unsolvable boundary-or, in the language of physicists, may experience a 'phase transition.' That means computational problems may remain solvable for extended periods regardless of the variables or conditions that are added, but at some point may become suddenly unsolvable-much like water remains a liquid despite falling temperatures until the thermometer reaches zero degrees centigrade, when the liquid then turns into ice.

Moreover, we concluded it's not the phase transition per se, but the nature of the transition that determines the level of complexity. A transition, for example, may be abrupt but simple (as in the case of water turning into ice), or abrupt but complex (as in the case of silicon turning into glass). The first transition is easy to understand; the second is not.

If our preliminary conclusions prove correct, more sophisticated understanding of NP-complete problems could have important implications for activities ranging from mathematicians' abstract understanding of algorithms to bottom-line efforts by airline executives to optimise their companies' flight schedules. It also may help physicists better understand the world in which we live by shedding new light on the behaviour of materials and complex systems.

When it comes to computational problems, our findings could help separate the analytical wheat from the chaff and, as a result, help scientists focus their attention on problems that are solvable instead of spinning their wheels on problems that are not. In the process, we hope to bring the worlds of mathematics, physics and computer science a bit closer to illustrate that at critical points in complex phase transitions, a little often can mean a lot.

Riccardo Zecchina
ICTP Condensed Matter Physics Group

For additional information about computational complexity and phase transitions, see R. Monasson, R. Zecchina, S. Kirpatrick, B. Selman and L. Troyanksy, "Determining computational complexity from characteristic phase transitions,'' and Philip W. Anderson, "Solving problems in finite time," Nature 400 (8 July 1999). Also George Johnson, "Separating Insolvable and Difficult," The New York Times, 13 July 1999.

News from ICTP is delighted to report that for the second time in the past four months, the work of ICTP researchers has received coverage in The New York Times and other major international newspapers and journals. See the previous issue of News from ICTP (Summer 1999), p. 2.

Back to Contents Forward to Commentary

Home