Name
Title | ||
|---|---|---|
Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations |
Abstract | ||
|---|---|---|
Satisfying spin-assignments of triangulations of a surface are states of minimum energy of the antiferromagnetic Ising model on triangulations which correspond (via geometric duality) to perfect matchings in cubic bridgeless graphs. In this work we show that it is NP-complete to decide whether or not a triangulation of a surface admits a satisfying spin-assignment, and that it is #P-complete to determine the number of such assignments. Our results imply that the determination of even the entropy of the Ising model on triangulations at the thermodynamical limit is already #P-hard. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.dam.2014.10.003 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Ising model,Triangulations,Groundstates,Parsimonious reduction,#P-complete | Graph,Discrete mathematics,Combinatorics,P-complete,Conjunctive normal form,Duality (optimization),Triangulation (social science),Ising model,True quantified Boolean formula,Mathematics,Antiferromagnetism | Journal |
Volume | Issue | ISSN |
210 | C | 0166-218X |
Citations | PageRank | References |
2 | 0.39 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea Jiménez | 1 | 8 | 4.13 |
| Marcos A. Kiwi | 2 | 169 | 24.15 |