Hostname: page-component-74656f9884-rngvg Total loading time: 0 Render date: 2026-11-06T01:45:15.845Z Has data issue: false hasContentIssue false

The Complexity of Ferromagnetic Ising with Local Fields

Published online by Cambridge University Press:  14 August 2006

LESLIE ANN GOLDBERG
Affiliation:
Department of Computer Science, University of Warwick, Coventry, CV4 7AL, UK
MARK JERRUM
Affiliation:
Division of Informatics, University of Edinburgh, JCMB, The King's Buildings, Edinburgh EH9 3JZ, UK
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider the complexity of approximating the partition function of the ferromagnetic Ising model with varying interaction energies and local external magnetic fields. Jerrum and Sinclair provided a fully polynomial randomized approximation scheme for the case in which the system is consistent in the sense that the local external fields all favour the same spin. We characterize the complexity of the general problem by showing that it is equivalent in complexity to the problem of approximately counting independent sets in bipartite graphs, thus it is complete in a logically defined subclass of #P previously studied by Dyer, Goldberg, Greenhill and Jerrum. By contrast, we show that the corresponding computational task for the $q$-state Potts model with local external magnetic fields and $q>2$ is complete for all of #P with respect to approximation-preserving reductions.

Information

Type
Paper
Copyright
© 2006 Cambridge University Press