Complexity Classification Of The Six-Vertex Model

2017/02/09 by Jin‐Yi Cai, Cai, Jin-Yi, Zhiguo Fu +3 · 1 citation
Computer Science · Mathematics · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Graph theory and applications #Random Matrices and Applications #Statistical Mechanics (cond-mat.stat-mech) #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.1702.02863

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

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.

Cited by

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

Related

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