|
Sandia
researcher Sorin Istrail and the
Ising model, developed by Ernst
Ising in 1926 as part of his PhD
dissertation. |
Some scientific problems simply cannot
be solved. One such problem was identified
in 2000 by computational biologist
Sorin Istrail at Sandia National Laboratories,
who proved that the solution of the
much-studied Ising model cannot be
extended to three dimensions (3D).
The original model, developed by Ernst
Ising in 1926 as part of his Ph.D.
dissertation, often is used to describe
wide-ranging changes in state, from
flocking birds to unison freezing
of water molecules. Ising conceived
of the model in one dimension; later,
Nobel laureate Lars Onsager extended
it to two dimensions. But the world's
top mathematical physicists failed
to provide the exact solution for
the 3D Ising model; its properties
can be determined numerically with
high accuracy, but not exactly, not
for any lattice, and not in terms
of elementary equations. Istrail explained
why, using a method called computational
intractability, which identifies problems
that cannot be solved in humanly feasible
time. Approximately 6,000 such problems
are known among all areas of science.
Scientific Impact:
The work eliminated scientific uncertainty
about the exactness of the 3D Ising
model, thus ensuring that scientists
would not waste time trying to solve
the unsolvable. Fundamental problems
in physics hinge on whether such models
are fully understood.
Social Impact: Because
most real-world problems occur in
3D, this work effectively eliminated
the possibility that the Ising Model
will ever have a direct social impact.
But indirectly, this work has saved
money by encouraging the direction
of scientific efforts toward other,
more fruitful areas.
Reference: "Statistical
Mechanics, Three-Dimensionality and
NP-completeness: Universality of Intractability
for the Partition Function of the
Ising Model Across Non-Planar Lattices,"
Proceedings of the 31st ACM Annual
Symposium on the Theory of Computing
(STOC 2000), May 21-23, 2000, Portland,
Oregon. ACM Press 2000.
URL: http://bartok.ucsc.edu/peter/java/ising/ising.html
http://www.cs.sandia.gov/~scistra/main.html
Technical Contact:
Daniel A Hitchcock, Mathematical,
Information, & Computational Sciences
Division, 301-903-6767
Press Contact: Jeff
Sherwood, DOE Office of Public Affairs,
202-586-5806
SC-Funding Office:
Office of Advanced Scientific Computing
Research |