Cooling-Rate Dependence for the Spin-Glass Ground-State Energy: Implications for Optimization by Simulated Annealing

The zero-temperature ground-state properties of five spin-glass models have been studied as a function of the cooling rate requivalent-..delta..T/t to speculate that this difference is related to the fact that the 2D models are not NP-complete while the other three models are.

Abstract

The zero-temperature ground-state properties of five spin-glass models have been studied as a function of the cooling rate $r=\frac{\ensuremath{-}\ensuremath{\Delta}T}{t}$. Here $\ensuremath{\Delta}T$ is the temperature decrement and $t$ is the time (in Monte Carlo steps) at each temperature $T$. For the 2D $\ifmmode\pm\else\textpm\fi{}J$ and Gaussian models, $E(r)={E}_{0}+{C}_{1}{r}^{x}$, where $x\ensuremath{\cong}0.25$, while for the 3D $\ifmmode\pm\else\textpm\fi{}J$, a two-layer $\ifmmode\pm\else\textpm\fi{}J$, and infinite-range models, $E(r)={E}_{0}\ensuremath{-}{C}_{2}{(\mathrm{inr})}^{\ensuremath{-}1}$. We speculate that this difference is related to the fact that the 2D models are not $\mathrm{NP}$-complete while the other three models are.