z-logo
Premium
The computational complexity of two‐state spin systems
Author(s) -
Goldberg Leslie Ann,
Jerrum Mark,
Paterson Mike
Publication year - 2003
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10090
Subject(s) - partition function (quantum field theory) , antiferromagnetism , partition (number theory) , ising model , polynomial , combinatorics , hyperbola , mathematics , physics , finite field , square (algebra) , spin (aerodynamics) , statistical physics , quantum mechanics , geometry , mathematical analysis , thermodynamics
The subject of this article is spin‐systems as studied in statistical physics. We focus on the case of two spins. This case encompasses models of physical interest, such as the classical Ising model (ferromagnetic or antiferromagnetic, with or without an applied magnetic field) and the hard‐core gas model. There are three degrees of freedom, corresponding to our parameters β, γ, and μ. Informally, β represents the weights of edges joining pairs of “spin blue” sites, γ represents the weight of edges joining pairs of “spin green” sites, and μ represents the weight of “spin green” sites. We study the complexity of (approximately) computing the partition function in terms of these parameters. We pay special attention to the symmetric case μ = 1. Exact computation of the partition function Z is NP‐hard except in the trivial case βγ = 1, so we concentrate on the issue of whether Z can be computed within small relative error in polynomial time. We show that there is a fully polynomial randomised approximation scheme (FPRAS) for the partition function in the “ferromagnetic” region βγ ≥ 1, but (unless RP = NP) there is no FPRAS in the “antiferromagnetic” region corresponding to the square defined by 0 < β < 1 and 0 < γ < 1. Neither of these “natural” regions—neither the hyperbola nor the square—marks the boundary between tractable and intractable. In one direction, we provide an FPRAS for the partition function within a region which extends well away from the hyperbola. In the other direction, we exhibit two tiny, symmetric, intractable regions extending beyond the antiferromagnetic region. We also extend our results to the asymmetric case μ ≠ 1. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 133–154, 2003

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here