

Back to Lab NewsTable of Contents
When a lake freezes over, how do trillions of randomly oriented water molecules know at almost the same time to align themselves into crystalline form? Similarly, when iron becomes magnetized, how do trillions of atoms know to align their spins almost instantly?
Sandia researcher Sorin Istrail (Photo by Randy Montoya)
The beststudied model in science to discuss these phase changes and, indeed, a wide variety of changes in state (neural networking, protein folding, flocking birds, beating heart cells, questions of economics, and more) is the Ising model, developed by Ernst Ising in 1926 as part of his PhD dissertation.
Ising conceived of a linear chain, composed of particles that have magnetic moments called ³spins² able to take an up or down position. Each particleıs spin influences the spins of the moments bordering it. The conception was expanded almost 20 years later into a twodimensional grid of upward or downward spins, each spin influencing the behavior of spins around it, with a wider application in the material world.
The model can be expanded to any threedimensional lattice model, and its properties figured out numerically with a high degree of accuracy. But not exactly. Not for the general case. As opposed to the known mathematical solutions for one or two dimensions, no one has been able to find an exact solution to any threedimensional lattice problem in terms of elementary equations you could look up in a math book.
The continued application of Isingıs model more than 8,000 papers published between 1969 to 1997 has tempted many scientists to extend the gridıs usefulness into three dimensions, the realm in which most realworld problems take place.
Now Sandia computational biologist Sorin Istrail has shown that the solution of Isingıs model cannot be extended into three dimensions for any lattice, and so exact solutions can never be found.
Sorin, who has just taken entrepreneurial leave from Sandia to accept the position of Senior Director of Informatics Research with Celera Genomics Corporation, says his paper will be published in May in the Proceedings of the Association for Computing Machineryıs (ACM) 2000 Symposium on the Theory of Computing.
Says Sorin, ³Naturally, itıs not as useful as finding the Holy Grail. We all wanna be like Lars [Onsager, the NobelPrize chemist who, in a mathematical tourdeforce, extended the Ising model solution from one dimension to two]. But at least no one now needs to spend time trying to solve the unsolvable.²
To prove that the solution could not be extended, Sorin resorted to a method called computational intractability, which identifies problems that cannot be solved in humanly feasible time. There are approximately 6,000 such problems known in all areas of science. They are all mathematically equivalent to each other. A solution to one would be a solution to all. Says Sorin, ³I showed that the Ising problem, for any lattice, is one of those problems. Therefore, it is computationally intractable.²
Nobel laureate Richard Feynman wrote in 1972 of the threedimensional Ising model that ³the exact solution for three dimensions has not yet been found.²
Other researchers who have tried read like a roll call of famous names in science and mathematics: Onsager, Kac, Feynman, Fisher, Kasteleyn, Temperley, Green, Hurst, and more recently Barahona.
Says Sorin, ³What these brilliant mathematicians and physicists failed to do, indeed cannot be done.²
As for Ising, whom Sorin describes as ³a genius,² the young GermanJewish scientist was barred from teaching when Hitler came to power. The modeler worked menial jobs and, though he survived World War II and taught afterwards in the United States, never published again.
Last modiŜed: April 20, 2000
View Sandia news releases and fact sheets