Complexity Classification of the Eight-Vertex Model

2017/02/25 by Jin‐Yi Cai, Cai, Jin-Yi, Zhiguo Fu +1 · 1 citation
Computer Science · Mathematics · #Algebraic structures and combinatorial models #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Markov Chains and Monte Carlo Methods #Quantum Computing Algorithms and Architecture #Statistical Mechanics (cond-mat.stat-mech)

paper · pdf · doi:10.48550/arxiv.1702.07938

openalex publication_date 2017/02/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove a complexity dichotomy theorem for the eight-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. For tractability, we find some new classes of problems computable in polynomial time. For #P-hardness, we employ Möbius transformations to prove the success of interpolations.

Cited by

• An LP Algorithm for Counting Eulerian Orientations Through the Lens of Quasi-polymorphism

Related

• Complexity Classification Of The Six-Vertex Model
• Approximability of the Eight-vertex Model
• A complexity dichotomy for partition functions with mixed signs
• Counting perfect matchings and the eight-vertex model
• New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification