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

DOI10.1016/J.DAM.2014.10.003zbMATH Open1339.05316OpenAlexW2091727548MaRDI QIDQ299048FDOQ299048

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

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

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)

Cites Work

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

Cited In (6)

• A class of generalized Tribonacci sequences applied to counting problems
• Exact enumeration of the ground states of a triangular Ising antiferromagnet
• Computational thresholds for the fixed-magnetization Ising model
• Polynomial degeneracy for the first \(m\) energy levels of the antiferromagnetic 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)