2017/04/05 by Jin‐Yi Cai, Cai, Jin-Yi, Zhiguo Fu +3
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.1704.01657
openalex publication_date 2017/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We discover new P-time computable six-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings. We further prove that there are no more: Together, they exhaust all P-time computable six-vertex models on planar graphs, assuming #P is not P. This leads to the following exact complexity classification: For every parameter setting in \mathbb C for the six-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) #P-hard for general graphs but computable in P-time for planar graphs, or (3) #P-hard even for planar graphs. The classification has an explicit criterion. The new P-time cases in (2) provably cannot be subsumed by Kasteleyn's algorithm. They are obtained by a non-local connection to #CSP, defined in terms of a "loop space". This is the first substantive advance toward a planar Holant classification with not necessarily symmetric constraints. We introduce Möbius transformation on \mathbb C as a powerful new tool in hardness proofs for counting problems.