2026-08-16T00:49:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8325 2024-03-06T10:42:01Z ddc:004 open_access

A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory Cai, Jin-Yi Fu, Zhiguo Girstmair, Kurt Kowalczyk, Michael Spin Systems Holant Problems Number Theory Characters Cyclotomic Fields 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jin-Yi Cai and Zhiguo Fu and Kurt Girstmair and Michael Kowalczyk 2018 Is Part Of LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2018.2 urn:nbn:de:0030-drops-83251 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.2 eng https://creativecommons.org/licenses/by/3.0/legalcode