The Library
The complexity of ferromagnetic ising with local fields
Tools
Tools
Tools
Goldberg, Leslie Ann and Jerrum, Mark (2007) The complexity of ferromagnetic ising with local fields. Combinatorics, Probability and Computing, Volume 16 (Number 1). pp. 43-61. doi:10.1017/S096354830600767X ISSN 0963-5483.
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.1017/S096354830600767X
Abstract
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.
| 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: | Combinatorics, Probability and Computing | ||||
| Publisher: | Cambridge University Press | ||||
| ISSN: | 0963-5483 | ||||
| Official Date: | January 2007 | ||||
| Dates: |
|
||||
| Volume: | Volume 16 | ||||
| Number: | Number 1 | ||||
| Number of Pages: | 19 | ||||
| Page Range: | pp. 43-61 | ||||
| DOI: | 10.1017/S096354830600767X | ||||
| 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 |
