The Library
The computational complexity of two-state spin systems
Tools
Tools
Tools
Goldberg, Leslie Ann, Jerrum, Mark and Paterson, Michael S. (2003) The computational complexity of two-state spin systems. Random Structures & Algorithms, Volume 23 (Number 2). pp. 133-154. doi:10.1002/rsa.10090 ISSN 1042-9832.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1002/rsa.10090
Abstract
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 beta, gamma, and mu. Informally, beta represents the weights of edges joining pairs of "spin blue" sites, gamma represents the weight of edges joining pairs of "spin green" sites, and mu 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 mu = 1. Exact computation of the partition function Z is NP-hard except in the trivial case betagamma = 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 betay greater than or equal to 1, but (unless RP = NP) there is no FPRAS in the "antiferromagnetic" region corresponding to the square defined by 0 < beta < 1and 0 < gamma < 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 mu not equal 1.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Journal or Publication Title: | Random Structures & Algorithms | ||||
| Publisher: | John Wiley & Sons, Inc. | ||||
| ISSN: | 1042-9832 | ||||
| Official Date: | September 2003 | ||||
| Dates: |
|
||||
| Volume: | Volume 23 | ||||
| Number: | Number 2 | ||||
| Number of Pages: | 22 | ||||
| Page Range: | pp. 133-154 | ||||
| DOI: | 10.1002/rsa.10090 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
