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."