Computational Hardness of Enumerating Satisfying Spin-Assignments in Triangulations

Details Computational Hardness of Enumerating Satisfying Spin-Assignments in Triangulations Computational Hardness of Enumerating Satisfying Spin-Assignments in Triangulations

2011-07-19

arxiv.org/abs/1107.3767v1

Computer Science

Computational Complexity

20 pages,25 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Computational Hardness of Enumerating Satisfying Spin-Assignments in Triangulations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computational Hardness of Enumerating Satisfying Spin-Assignments in Triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computational Hardness of Enumerating Satisfying Spin-Assignments in Triangulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-515019