A complexity classification of spin systems with an external field

作者：Goldberg Leslie Ann; Jerrum Mark^*

来源：Proceedings of the National Academy of Sciences of the United States of America, 2015, 112(43): 13161-13166.

DOI：10.1073/pnas.1505664112

• computational complexity
• partition function
• spin system

We study the computational complexity of approximating the partition function of a q-state spin system with an external field. There are just three possible levels of computational difficulty, depending on the interaction strengths between adjacent spins: (i) efficiently exactly computable, (ii) equivalent to the ferromagnetic Ising model, and (iii) equivalent to the antiferromagnetic Ising model. Thus, every nontrivial q-state spin system, irrespective of the number q of spins, is computationally equivalent to one of two fundamental two-state spin systems.

• 出版日期2015-10-27