History

Please fill in your query. A complete syntax description you will find on the General Help page.
Approximability of the ground state problem for certain Ising spin glasses. (English)
J. Complexity 13, No.3, 326-339 (1997).
Summary: The authors consider polynomial time algorithms for finding approximate solutions to the ground state problem for the following three-dimensional case of an Ising spin glass: $2n$ spins are arranged on a two-level grid with at most $n^γ$ vertical interactions $(0\leγ\leq 1)$. The main results are: 1. Let $\frac 12\leq γ< 1$. There is an approximate polynomal time algorithm with absolute error less than $n^γ$ for all $n$; there exists a constant $β> 0$ such that every approximate polynomial time algorithm has absolute error greater than $βn^γ$ infinitely often, unless P = NP. 2. Let $γ= 1$. There is an approximate polynomial time algorithm with absolute error less than $n/\lg n$; there exists a number $k> 1$ such that every approximate polynomial time algorithm has absolute error greater than $n/(\lg n)^k$ infinitely often iff $\text{NP}\nsubseteq \bigcap_{ε> 0} \text{DTIME} (2^{n^ε})$.
Classification: G.4