When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2018.2
URN: urn:nbn:de:0030-drops-83251
URL: http://drops.dagstuhl.de/opus/volltexte/2018/8325/
 Go to the corresponding LIPIcs Volume Portal

### A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory

 pdf-format:

### 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.

### BibTeX - Entry

@InProceedings{cai_et_al:LIPIcs:2018:8325,
author =	{Jin-Yi Cai and Zhiguo Fu and Kurt Girstmair and Michael Kowalczyk},
title =	{{A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory}},
booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages =	{2:1--2:22},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-060-6},
ISSN =	{1868-8969},
year =	{2018},
volume =	{94},
editor =	{Anna R. Karlin},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},