Journal de Physique Lettres · 1985 · 79 citations · 3 references
Natural SciencesMathematicsPhysicsComputational PhysicsCondensed Matter PhysicsPhase TransformationsAntiferromagnetismComputational ComplexityCritical PhenomenaFerromagnetismPhase TransitionsStatistical MechanicsAntiferromagnetic TransitionsComplexityFerromagnetic Phase TransitionsFrustrated AntiferromagnetsIsing AntiferromagnetIsing MagnetismIsing ModelIsing Model Formulation
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.
3
Optimization by Simulated Annealing
Scott Kirkpatrick, C. D. Gelatt, M.P. Vecchi · Science · 1983 · 44.6K citations
Maximal Flow Through a Network
L. R. Ford, D. R. Fulkerson · Canadian Journal of Mathematics · 1956 · 2.3K citations · Full text