Complexity classification of the six-vertex model

DOI10.1016/J.IC.2018.01.003MaRDI QIDQ1706146zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Zhiguo Fu, Mingji Xia

Publication date 21 March 2018

Published in Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

interpolationspin systemsix-vertex modelHolant problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: We prove a complexity dichotomy theorem for the six-vertex model. For every setting of the parameters of the model, we prove that computing the partition function is either solvable in polynomial time or #P-hard. The dichotomy criterion is explicit.

Recommendations

• Approximability of the Six-vertex Model
• The complexity of partition functions
• Automata, Languages and Programming
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• A complexity dichotomy for hypergraph partition functions

Cites work

• scientific article; zbMATH DE number 1369835 (Why is no real title available?)
• A complete dichotomy rises from the capture of vanishing signatures (extended abstract)
• A dichotomy for real weighted Holant problems
• Computational complexity of Holant problems
• Correlation decay up to uniqueness in spin systems
• Dichotomy for Holant* problems of Boolean domain
• Expressiveness of matchgates.
• Holographic Algorithms
• Markov chain algorithms for planar lattice structures
• On the evaluation at (3,3) of the Tutte polynomial of a graph
• On the number of Eulerian orientations of a graph
• Polynomial-Time Approximation Algorithms for the Ising Model
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Reflection positivity, rank connectivity, and homomorphism of graphs
• The complexity of complex weighted Boolean \#CSP
• The computational complexity of two‐state spin systems

Cited in

(5)

• Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS
• scientific article; zbMATH DE number 7650104 (Why is no real title available?)
• Approximability of the Six-vertex Model
• Beyond windability: approximability of the four-vertex model
• Complexity classification of the eight-vertex model

This page was built for publication: Complexity classification of the six-vertex model

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