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

Cai, Jin-Yi; Fu, Zhiguo; Girstmair, Kurt; Kowalczyk, Michael

doi:10.4230/LIPIcs.ITCS.2018.2

Document

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

Authors Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, Michael Kowalczyk

Part of: Volume: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Innovations in Theoretical Computer Science Conference (ITCS)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2018-01-12

PDF

File

PDF

LIPIcs.ITCS.2018.2.pdf

Filesize: 0.55 MB
22 pages

Document Identifiers

DOI: 10.4230/LIPIcs.ITCS.2018.2
URN: urn:nbn:de:0030-drops-83251

Subject Classification

Keywords

Spin Systems
Holant Problems
Number Theory
Characters
Cyclotomic Fields

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get 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

Author Details

Jin-Yi Cai

Zhiguo Fu

Kurt Girstmair

Michael Kowalczyk

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail