Physics Bumps Up Against the Unsolvable

Physicists have been searching for decades for a simple, mathematical solution to a model of phase transitions. Such transitions occur, for instance, when ice melts or cooling iron becomes magnetic. Now it looks as though the search was in vain: A computer scientist has shown that the problem can't be solved except by brute-force calculations.

The Ising model was introduced in 1920 to simulate how small-scale changes, such as interactions between atoms, can contribute to large-scale order, such as whether a sliver of iron will be magnetic. The model lays out sim-atoms in a 3D lattice. To model a given phase transition, researchers must count up all the possible atom-level arrangements and pick the one with the lowest energy level. It's a slow, inefficient process.

Unfortunately, as theoretical computer scientist Sorin Istrail of Celera Genomics in Rockville, Maryland, shows, a simpler solution is not at hand. While working at Sandia National Laboratories, he translated the Ising model into the language of graph theory, in essence defining the problem as a set of points and edges. The 3D graph--as opposed to the solvable 1D or 2D Ising models--can't be drawn as a plane. Istrail then showed that nonplanar graphs fall into the realm of a class of recalcitrant calculations that theorists believe can be solved only by arduous calculations. "What these brilliant mathematicians and physicists failed to do, indeed can't be done," says Istrail.

The report, presented at an Association for Computing Machinery meeting in Portland, Oregon, is disappointing for researchers who had awaited a simple answer, which people have always thought "was just around the corner," says computational physicist Alan Ferrenberg of the University of Georgia, Athens. "It really means now that numerical analysis is the only way you've got to approach" the problem.