On the approximability of the energy function of Ising spin glasses
Alberto Bertoni, Paola Campadelli, Giuseppe Molteni · Journal of Physics A Mathematical and General · 1994
We consider polynomial-time algorithms for finding approximate solutions to the ground-state problem for the following three-dimensional case of an Ising spin glass: n spins are arranged on a two-level grid with n vertical interactions. The main results are: (i) there is an approximate polynomial-time algorithm with absolute error less than n, for all n; and (ii) there exists a constant alpha >0 such that every approximate polynomial-time algorithm has absolute error greater than alpha square root n infinitely often, unless P=NP.