# Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intracatability for the partition function of the Ising model across non-planar surfaces (extended abstract)

@inproceedings{Istrail2000StatisticalMT, title={Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intracatability for the partition function of the Ising model across non-planar surfaces (extended abstract)}, author={Sorin Istrail}, booktitle={STOC '00}, year={2000} }

This work provides an exact characterization, across crystal lattices, of the computational tractability frontier for the partition functions of several Ising models. Our results show that beyond planarity computing partition functions is NP-complete. We provide rigorous solutions to several working conjectures in the statistical mechanics literature, such as the Crossed-Bonds conjecture, and the impossibility to compute effectively the partition functions for any three-dimensional lattice… Expand

#### Figures and Topics from this paper

#### 94 Citations

The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity

- Mathematics, Computer Science
- COLT
- 2018

A simple and optimal bound is provided for the KL error of the mean field approximation for Ising models on general graphs, and it is shown that approximation within $(n \|J\|_F)^{1-\delta}$ is NP-hard for every $\delta > 0$. Expand

Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average

- Mathematics, Physics
- 2020 IEEE International Symposium on Information Theory (ISIT)
- 2020

We establish the average-case hardness of the algorithmic problem of exactly computing the partition function of the Sherrington-Kirkpatrick model of spin glasses with Gaussian couplings. In… Expand

Counting Self-avoiding Walks in Some Regular Graphs

- 2004

Figure 1: A length-18 in the complete 2D grid. lems in different areas of science, such as combinatorics, statistical physics, theoretical chemistry, and computer science. By “twodimensional grid” we… Expand

Title Commuting quantum circuits and complexity of Ising partitionfunctions

- 2018

Instantaneous quantumpolynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal. Nevertheless, it has been shown that if… Expand

Commuting quantum circuits and complexity of Ising partition functions

- 2017

Instantaneous quantumpolynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal. Nevertheless, it has been shown that if… Expand

Quantum Commuting Circuits and Complexity of Ising Partition Functions

- Physics, Mathematics
- ArXiv
- 2013

It is shown that there is no fully polynomial randomized approximation scheme (FPRAS) for Ising models with almost all imaginary coupling constants even on a planar graph of a bounded degree, unless the PH collapses at the third level. Expand

The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes

- Mathematics, Computer Science
- Theor. Comput. Sci.
- 2003

This paper offers a partial answer to the question of Welsh: it is #P-complete to compute the number of self-avoiding walks of a given length in a subgraph of a two-dimensional grid. Expand

Hardness of parameter estimation in graphical models

- Computer Science, Mathematics
- NIPS
- 2014

The main result shows that parameter estimation is in general intractable: no algorithm can learn the canonical parameters of a generic pair-wise binary graphical model from the mean parameters in time bounded by a polynomial in the number of variables. Expand

Dimer problem for some three dimensional lattice graphs

- Mathematics
- 2016

Dimer problem for three dimensional lattice is an unsolved problem in statistical mechanics and solid-state chemistry. In this paper, we obtain asymptotical expressions of the number of close-packed… Expand

Aspects of confinement in QCD from lattice simulations

- Physics
- 2010

We study confinement in quantum chromodynamics via numerical simulations in the framework of lattice gauge theory. In Landau gauge, the mechanism of confinement is related to the infrared behavior of… Expand

#### References

SHOWING 1-10 OF 59 REFERENCES

Crystal statistics. I. A two-dimensional model with an order-disorder transition

- Physics
- 1944

The partition function of a two-dimensional "ferromagnetic" with scalar "spins" (Ising model) is computed rigorously for the case of vanishing field. The eigenwert problem involved in the… Expand

On the computational complexity of Ising spin glass models

- Mathematics
- 1982

In a spin glass with Ising spins, the problems of computing the magnetic partition function and finding a ground state are studied. In a finite two-dimensional lattice these problems can be solved by… Expand

Combinatorial Aspects of the Ising Model for Ferromagnetism. I. A Conjecture of Feynman on Paths and Graphs

- Mathematics
- 1960

An identity on paths in planar graphs conjectured by Feynman [H] is rigorously established. This permits a complete analysis of the combinatorial approach to the two‐dimensional Ising model with… Expand

Statistics of the Two-Dimensional Ferromagnet. Part II

- Physics
- 1941

In an effort to make statistical methods available for the treatment of cooperational phenomena, the Ising model of ferromagnetism is treated by rigorous Boltzmann statistics. A method is developed… Expand

Applicability of the Pfaffian Method to Combinatorial Problems on a Lattice

- Mathematics
- 1964

For the solution of certain problems in statistical mechanics, a formulation in terms of the combinatorial problem of counting open or closed polygons drawn on a lattice has been found useful. The… Expand

On the Dimer Solution of Planar Ising Models

- Physics
- 1966

Derivations of the partition function of the Ising model on a general planar lattice L, which proceed via an associated dimer problem and use Pfaffians, are simplified by constructing a lattice LΔ… Expand

Simple Ising models still thrive

- Mathematics
- 1981

A selection of recent work by various authors concerning spin 12; Ising modls with pair couplings is reviewed. Topics addressed include: the universality of corrections-to-scaling and nonlinear… Expand

The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice

- Mathematics
- 1961

Abstract The number of ways in which a finite quadratic lattice (with edges or with periodic boundary conditions) can be fully covered with given numbers of “horizontal” and “vertical” dimers is… Expand

Relation between the Onsager and Pfaffian Methods for Solving the Ising Problem. I. The Rectangular Lattice

- Physics
- 1965

An algebraic proof is given showing the equivalence of the Pfaffian and Onsager methods of solution of the Ising problem for the two‐dimensional rectangular lattice with free edge conditions. With… Expand

The Statistics of Dimers on a Lattice

- Physics
- 1961

The number of ways in which a finite quadratic lattice (with edges or with periodic boundary conditions) can be fully covered with given numbers of “horizontal” and “vertical” dimers is rigorously… Expand