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.