New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915794079711232 |
|---|---|
| author | Fan, Austen Cai, Jin-Yi Shao, Shuai Tang, Zhuxiao |
| author_facet | Fan, Austen Cai, Jin-Yi Shao, Shuai Tang, Zhuxiao |
| contents | We prove a complete complexity classification theorem for the planar eight-vertex model. For every parameter setting in ${\mathbb C}$ for the eight-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. In (2), we discover new P-time computable eight-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings. They are obtained by a combinatorial transformation to the planar {\sc Even Coloring} problem followed by a holographic transformation to the tractable cases in the planar six-vertex model. In the process, we also encounter non-local connections between the planar eight vertex model and the bipartite Ising model, conformal lattice interpolation and Möbius transformation from complex analysis. The proof also makes use of cyclotomic fields. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_11292 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model Fan, Austen Cai, Jin-Yi Shao, Shuai Tang, Zhuxiao Computational Complexity F.0 We prove a complete complexity classification theorem for the planar eight-vertex model. For every parameter setting in ${\mathbb C}$ for the eight-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. In (2), we discover new P-time computable eight-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings. They are obtained by a combinatorial transformation to the planar {\sc Even Coloring} problem followed by a holographic transformation to the tractable cases in the planar six-vertex model. In the process, we also encounter non-local connections between the planar eight vertex model and the bipartite Ising model, conformal lattice interpolation and Möbius transformation from complex analysis. The proof also makes use of cyclotomic fields. |
| title | New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model |
| topic | Computational Complexity F.0 |
| url | https://arxiv.org/abs/2602.11292 |