1982/10/01 by Francisco Barahona · 5 citations
Physics and Astronomy · Computer Science · Mathematics · #Theoretical and Computational Physics #Topological and Geometric Data Analysis #Random Matrices and Applications #Ising model #Spin glass #Spins #Bounded function #Ising spin #Lattice (music) #Partition function (quantum field theory) #Computational complexity theory #Time complexity #Mathematics #Complexity class #Square-lattice Ising model #Polynomial #Ground state #Magnetic field #Combinatorics #Discrete mathematics #Statistical physics #Condensed matter physics #Physics #Quantum mechanics #Algorithm #Mathematical analysis
paper · pdf · doi:10.1088/0305-4470/15/10/028
openalex publication_date 1982/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.