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

DOI10.1016/j.dam.2014.10.003zbMath1339.05316OpenAlexW2091727548MaRDI QIDQ299048

Andrea Jiménez, Marcos A. 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

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Constructing SAT Filters with a Quantum Annealer ⋮ A class of generalized Tribonacci sequences applied to counting problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponentially many perfect matchings in cubic graphs
• Towards a theory of frustrated degeneracy.
• Complexity of generalized satisfiability counting problems
• Satisfying states of triangulations of a convex \(n\)-gon
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Polynomial-Time Approximation Algorithms for the Ising Model
• Statistical mechanics, three-dimensionality and NP-completeness
• The Complexity of Enumeration and Reliability Problems
• The critical exponents of the two-dimensional Ising spin glass revisited: exact ground-state calculations and Monte Carlo simulations
• The complexity of satisfiability problems

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