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.

The aforementioned claims are derived via elaborate (and atypical) reductions that map a Boolean formula in conjunctive normal form into triangulations of orientable closed surfaces. Moreover, the novel reduction technique enables us to prove that even very constrained versions of #MaxCut are already #P-hard. (C) 2014 Elsevier B.V. All rights reserved