Resources

- S. Istrail, Statistical Mechanics, Three-Dimensionality and NP-Completeness: I. Universality of Intractability of the Partition Functions of the Ising Model Across Non-Planar Lattices
- The Ising Model at Wikipedia
- One of the 100 most important discoveries supported by the Office of Science of DOE - Identifying an Intractable Scientific Problem [parent article]
- Dr. Ernst Ising Obituary at Bradley University
- Identifying an Intractable Scientific Problem U.S. Department of Energy, Office of Science News Release
- The Ising Model is NP-complete, by Barry Cipra SIAM News, vol. 33, No. 6
- MATHEMATICS: Statistical Physicists Phase Out a Dream, by Barry Cipra Science, vol. 288, pp. 5471
- PHYSICS: The Ising on the Cake, by Philip Ball Nature

### Combinatorial Roots of Phase Transition: Statistical Mechanics and Complexity Theory

The Ising model, the most studied model in statistical mechanics,
is the ultimate model for studying phase transition. The deepest
result of the area is due to Onsager, who obtained in 1944 the
analytical closed form of the partition function for the
two-dimensional square lattice model. This exact solubility provided
the exact formula for the phase transition critical point. His
monumental achievement generated an enormous search for
generalizations to three-dimensions. Under the leadership of Marc Kac,
Michael Fisher, Richard Feynman, this research effort successfully
extended the methods to all planar models, but failed to find any
exactly solvable three-dimensional model. As the absence of exact
solubility results for three-dimensional models is common in
statistical physics, Sorin's negative “solution” in 2000 for
the three-dimensional Ising model provided a first answer towards the
qualitative analytical roadblocks to phase transition solubility. Sorin's
complete characterization – for every translational-invariant
non-planar lattice model computing the partition function is
NP-complete – provided the answer that *non-planarity,
*and not* dimensionality, *is the frontier of analytical
intractability*. *It turns out that the uncovered combinatorial
roots of difficulty for the Ising model are responsible for a much
wider phenomenon implying qualitatively identical results for the
Dimers, Ice, Percolation and Self-Avoiding Walks models.