title: A complexity classification of spin systems with an external field.
abstract: We study the computational complexity of approximating the partition function of a q-state spin system with an external field. There are just three possible levels of computational difficulty, depending on the interaction strengths between adjacent spins: (i) efficiently exactly computable, (ii) equivalent to the ferromagnetic Ising model, and (iii) equivalent to the antiferromagnetic Ising model. Thus, every nontrivial q-state spin system, irrespective of the number q of spins, is computationally equivalent to one of two fundamental two-state spin systems.
authors.affiliation: Department of Computer Science, University of Oxford, Oxford OX1 3QD, United Kingdom;
authors.forename: Leslie Ann
authors.initials: LA
authors.lastname: Goldberg
authors.affiliation: School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, United Kingdom m.jerrum@qmul.ac.uk.
authors.forename: Mark
authors.initials: M
authors.lastname: Jerrum
keywords: computational complexity; partition function; spin system