The random field Ising model : algorithmic complexity and phase transition

Abstract

The random field Ising model (RFIM) is investigated from the complexity point of view. We prove that finding a ground state of the ferromagnetic RFIM is a polynomial (P) optimization problem in any dimension d. A new rigidity algorithm for the search of the ground state morphology is also given. In contrast, the problem associated to the antiferromagnetic RFIM is shown to be an NP-complete optimization problem. The absence of any sensivity to d contrasts sharply with the known results previously obtained for the frustration model of spin glasses. Our results show, in particular, the absence of a simple one to one correspondence between finite Tc phase transition and NP-completeness properties in statistical mechanics models with competing interactions.