Goldberg, Leslie Ann, Jerrum, Mark and Paterson, Michael S. (2001) The computational complexity of two-state spin systems. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Preview

PDF (Department of Computer Science Research Report) WRAP_cs-rr-386.pdf - Other - Requires a PDF viewer. Download (465Kb) | Preview

Request Changes to record.

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. We wish to study the complexity of (approximately) computing the partition function in terms of these parameters. We pay special attention to the symmetric case mu=1 for which our results are depicted in Figure 1. Exact computation of the partition function Z is NP-hard except in the trivial case beta gamma=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 beta gamma >= 1, but (unless RP=NP) there is no FPRAS in the "antiferromagnetic" region corresponding to the square defined by 0<beta<1 and 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 to 1.

Item Type:	Report
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH):	Statistical physics, Spin waves
Series Name:	Department of Computer Science research report
Publisher:	University of Warwick. Department of Computer Science
Official Date:	29 November 2001
Dates:	Date Event 29 November 2001 Completion
Number:	Number 386
Number of Pages:	19
DOI:	CS-RR-386
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Status:	Not Peer Reviewed
Publication Status:	Unpublished
Funder:	Engineering and Physical Sciences Research Council (EPSRC), Fifth Framework Programme (European Commission) (FP5)
Grant number:	GR/R44560/01 (EPSRC), IST-1999-14186 (FP5), IST- 1999-14036 (FP5)
Related URLs:	Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item