Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations

DOI10.1016/J.DAM.2014.10.003MaRDI QIDQ299048zbMATH OpenOpenAlexFDO

Authors Andrea Jiménez, Marcos Kiwi

Publication date 22 June 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2014.10.003

zbMATH Keywords

triangulationsIsing model\(\# \operatorname{P}\)-completenessgroundstatesparsimonious reduction

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Recommendations

• Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings
• Statistical mechanics, three-dimensionality and NP-completeness
• The computational complexity of two‐state spin systems
• The Complexity of Ferromagnetic Ising with Local Fields
• Exact enumeration of the ground states of a triangular Ising antiferromagnet

Cites work

• scientific article; zbMATH DE number 15994 (Why is no real title available?)
• scientific article; zbMATH DE number 5029233 (Why is no real title available?)
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of generalized satisfiability counting problems
• Discrete mathematics in statistical physics. Introductory lectures
• Exponentially many perfect matchings in cubic graphs
• Graphs on surfaces
• Polynomial-Time Approximation Algorithms for the Ising Model
• Satisfying states of triangulations of a convex \(n\)-gon
• Statistical mechanics, three-dimensionality and NP-completeness
• The Complexity of Enumeration and Reliability Problems
• The complexity of satisfiability problems
• The critical exponents of the two-dimensional Ising spin glass revisited: exact ground-state calculations and Monte Carlo simulations
• Towards a theory of frustrated degeneracy.

Cited in

(6)

• A class of generalized Tribonacci sequences applied to counting problems
• Exact enumeration of the ground states of a triangular Ising antiferromagnet
• Polynomial degeneracy for the first \(m\) energy levels of the antiferromagnetic Ising model
• Computational thresholds for the fixed-magnetization Ising model
• Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings
• Constructing SAT filters with a quantum annealer

This page was built for publication: Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q299048)