On the computational complexity of Ising spin glass models

Abstract

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 algorithms that require a number of steps bounded by a polynomial function of the size of the lattice. In contrast to this fact, the same problems are shown to belong to the class of NP-hard problems, both in the two-dimensional case within a magnetic field, and in the three-dimensional case. NP-hardness of a problem suggests that it is very unlikely that a polynomial algorithm could exist to solve it. © 1982 The Japan Society of Applied Physics.