  Satisfying spin-assignments in 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
surface triangulation admits a satisfying spin-assignment, and that it is
#P-complete to determine the number of such assignments. Both results are
derived via an elaborate (and atypical) reduction that maps a Boolean formula
in 3-conjunctive normal form into a triangulation of an orientable closed
surface.
