Approximability of the Ground State Problem for Certain Ising Spin Glasses

We consider polynomial time algorithms for finding approximate solutions to the groundstateproblem for the following three-dimensional case of an Isingspinglass: 2nspins are arranged on a two-level grid with at mostnγvertical interactions (0 ≤ γ ≤ 1). The main results are:1. Let≤ γ < 1. There is an approximate polynomial time algorithm with absolute error less thannγfor alln; there exists a constant β > 0 such that every approximate polynomial time algorithm has absolute error greater than βnγinfinitely often, unlessP=NP.2. Let γ = 1. There is an approximate polynomial time algorithm with absolute error less thann/lgn; there exists a numberk> 1 such that every approximate polynomial time algorithm has absolute error greater thann/(lgn)kinfinitely often iffNP⊈ ∩ε > 0DTIME(2nε).