J. Physique Lett. 46, 173-180 (1985)
DOI: 10.1051/jphyslet:01985004605017300

The random field Ising model : algorithmic complexity and phase transition

J.C. Angles d'Auriac, M. Preissmann et R. Rammal

Centre de Recherches sur les Très Basses Températures, CNRS, 25, avenue des Martyrs, B.P. 166 X, 38042 Grenoble Cedex, France

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.

Résumé
Le modèle d'Ising en champ aléatoire (RFIM) est étudié du point de vue de la complexité algorithmique. On montre que le problème d'optimisation de la recherche d'un état de base du modèle ferromagnétique est polynomial (P) en toutes dimensions. Un nouvel algorithme de rigidité pour l'étude de la morphologie des états de base est aussi donné. Par opposition, le problème associé au modèle antiferromagnétique est démontré être NP-complet. L'absence d'une dépendance explicite de la complexité du RFIM avec la dimensionnalité contraste avec les résultats connus pour le modèle de frustration des verres de spins. Nos résultats montrent en particulier l'absence d'une correspondance simple entre les propriétés : NP-complet et existence d'une transition de phase a Tc fini dans les modèles de mécanique statistique avec des interactions en compétition.

PACS
0550 - Lattice theory and statistics: Ising problems.
7540 - Critical point effects, specific heats, short range order in magnetic materials.

Key words
antiferromagnetism -- ferromagnetism -- Ising model -- magnetic transitions -- polynomial optimisation problem -- random field Ising model -- algorithmic complexity -- phase transition -- ground state -- ferromagnetic RFIM -- rigidity algorithm -- ground state morphology -- antiferromagnetic RFIM -- NP complete optimization problem -- statistical mechanics models -- competing interactions