The complexity of ferromagnetic two-spin systems with external fields

DOI10.4230/LIPICS.APPROX-RANDOM.2014.843MaRDI QIDQ2969666zbMATH OpenOpenAlexFDO

Authors Jing-Cheng Liu, Pinyan Lu, Chihao Zhang

Publication date 22 March 2017

Full work available at URL https://arxiv.org/abs/1402.4346

zbMATH Keywords

\#BIS-hardFPRASspin system

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Statistical mechanics of magnetic materials (82D40)

Abstract: We study the approximability of computing the partition function for ferromagnetic two-state spin systems. The remarkable algorithm by Jerrum and Sinclair showed that there is a fully polynomial-time randomized approximation scheme (FPRAS) for the special ferromagnetic Ising model with any given uniform external field. Later, Goldberg and Jerrum proved that it is #BIS-hard for Ising model if we allow inconsistent external fields on different nodes. In contrast to these two results, we prove that for any ferromagnetic two-state spin systems except the Ising model, there exists a threshold for external fields beyond which the problem is #BIS-hard, even if the external field is uniform.

Recommendations

• The Complexity of Ferromagnetic Ising with Local Fields
• A complexity classification of spin systems with an external field
• The computational complexity of two‐state spin systems
• Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

Cited in

(10)

• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
• Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• A complexity classification of spin systems with an external field
• The Complexity of Ferromagnetic Ising with Local Fields
• Counting constraint satisfaction problems
• Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Approximation Algorithms for the Random Field Ising Model
• The complexity of ferromagnetic 2-spin systems on bounded degree graphs

This page was built for publication: The complexity of ferromagnetic two-spin systems with external fields

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