LIPIcs.ITCS.2018.2.pdf
- Filesize: 0.55 MB
- 22 pages
Document
A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
Authors
-
Part of:
Volume:
9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Innovations in Theoretical Computer Science Conference (ITCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-01-12
Cite AsGet BibTex
Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, and Michael Kowalczyk. A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ITCS.2018.2
https://doi.org/10.4230/LIPIcs.ITCS.2018.2
Abstract
Suppose \varphi and \psi are two angles satisfying \tan(\varphi) = 2 \tan(\psi) > 0. We prove that under this condition \varphi and \psi cannot be both rational multiples of \pi. We use this number theoretic result to prove a classification of the computational complexity of spin systems on k-regular graphs with general (not necessarily symmetric) real valued edge weights. We establish explicit criteria, according to which the partition functions of all such systems are classified into three classes: (1) Polynomial time
computable, (2) \#P-hard in general but polynomial time computable
on planar graphs, and (3) \#P-hard on planar graphs. In particular problems in (2) are precisely those that can be transformed to a form solvable by the Fisher-Kasteleyn-Temperley algorithm by a holographic reduction.
Keywords
- Spin Systems
- Holant Problems
- Number Theory
- Characters
- Cyclotomic Fields
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads