Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.
GoldBio

BROWN UNIVERSITY   Alerts | Access Rights | My Account | Sign In
Subscribe

Science 2 June 2000:
Vol. 288. no. 5471, pp. 1561 - 1562
DOI: 10.1126/science.288.5471.1561a

News of the Week

MATHEMATICS:
Statistical Physicists Phase Out a Dream

Barry Cipra

For decades, the Holy Grail of statistical mechanics has been a mathematical problem known as the Ising model. Introduced in the 1920s by German physicist Ernst Ising, the Ising model is a powerful tool for studying phase transitions: the abrupt changes of state that occur, for instance, when ice melts or cooling iron becomes magnetic. Although they've learned much from approximate solutions and computer simulations, physicists have long sought an exact mathematical solution to the Ising model, which would provide much more information about such still-mysterious transitions.

Unfortunately, it looks as if that's not in the cards. Sorin Istrail, a theoretical computer scientist at Celera Genomics in Rockville, Maryland, has proved that the Ising model --at least in its most general, three- dimensional (3D) form--belongs to a class of problems that theorists believe will remain unsolved forever. "People have always thought the 3D solution was just around the corner," says Alan Ferrenberg, a computational physicist at the University of Georgia, Athens. "It really means now that numerical analysis is the only way we've got to approach [the Ising model]."

The Ising model deals with objects--say, atoms--laid out in a regular array, such as a rectangular grid or a honeycomb arrangement. The array can be 1D (think of beads on a string), a 2D grid, or a 3D lattice. What makes the model so useful is that it helps physicists understand how a large system of objects, each interacting only with its nearest neighbors, can combine to create a large-scale order. In a ferromagnet, for example, each atom has a magnetic moment that points either up or down. Pairs of neighbors with opposing moments raise the total energy of the system, while those with parallel moments lower it.

Solving the model means counting the number of arrangements that add up to each given energy level. Some versions of the Ising model can be solved exactly. Ising himself solved the 1D ferromagnetic model--and found it had no phase transition. In 1944, the Norwegian chemist Lars Onsager discovered an exact formula for the 2D model, which does possess a phase transition. But scientists have never been able to extend Ising's and Onsager's solutions to the physically realistic realm of three dimensions. "We now know why," says Istrail. "What these brilliant mathematicians and physicists failed to do, indeed cannot be done."

While working at Sandia National Laboratories, Istrail proved that computing the energy states for the general 3D Ising model is what computer scientists call an NP-complete problem--one of a class of recalcitrant calculations that theorists believe can be solved only by arduous brute-force computations. In effect, an exact solution to the Ising model would provide the key to efficient algorithms for solving thousands of other computational problems, ranging from factoring large numbers to the notorious traveling salesman problem, in which the salesman must find the most efficient route through a given number of cities. Although no one has proved that such a sweeping solution is impossible, theorists are fairly certain the NP-complete problems really are as hard as they seem to be. If so, the 3D Ising model is intractable, too.

To reach that dismaying conclusion, Istrail started by translating the Ising model into terms of graph theory. A mathematical graph is just a collection of points called "vertices," pairs of which are connected by "edges"--just as in the Ising model pairs of neighboring atoms are linked by the interactions between them. The edges may be weighted with numerical values. In the traveling salesman problem, for example, the weights are the distances between pairs of cities. For the Ising model, the weights describe the amount by which parallel or opposing magnetic moments of neighboring atoms increase or decrease the energy.

Computing the lowest energy state for the Ising model, it turns out, is equivalent to cutting the corresponding graph in two by plucking off the edges whose weights add up to the smallest possible number. For planar graphs--that is, graphs that can be drawn on a piece of paper without any of the edges crossing--that calculation is a relative breeze. But 3D lattices are inherently nonplanar, and that, Istrail recognized, is the key. He has shown that any nonplanar graph throws up a barrier of computational intractability.

It might still be possible to find exact answers for some special cases of the Ising model, Istrail notes. In particular, the ferromagnetic case of the 3D Ising model may turn out to be simple enough to solve. Nevertheless, the overall message is clear. "We need a paradigm shift," Istrail says. "Instead of waiting for the mathematics to advance, we have to accept this impossibility." And the computational complexity of the Ising model could be just the tip of the iceberg. "There is something about this world that doesn't allow us to understand it."





ADVERTISEMENT

Advertisement

ADVERTISEMENT

Featured Jobs

Science. ISSN 0036-8075 (print), 1095-9203 (online)