Barahona's work discusses the computational complexity of Ising spin glass models. In a spin glass with Ising spins, the computation of the magnetic partition function and finding the ground state are examined. For finite two-dimensional lattices, these problems can be solved by algorithms with a number of steps bounded by a polynomial function of the lattice size. However, these problems are shown to be NP-hard in both two and three dimensions, even in the presence of a magnetic field. NP-hardness implies that it is unlikely a polynomial-time algorithm exists to solve these problems. The study was published in 1982 by the Japan Society of Applied Physics.Barahona's work discusses the computational complexity of Ising spin glass models. In a spin glass with Ising spins, the computation of the magnetic partition function and finding the ground state are examined. For finite two-dimensional lattices, these problems can be solved by algorithms with a number of steps bounded by a polynomial function of the lattice size. However, these problems are shown to be NP-hard in both two and three dimensions, even in the presence of a magnetic field. NP-hardness implies that it is unlikely a polynomial-time algorithm exists to solve these problems. The study was published in 1982 by the Japan Society of Applied Physics.