1.
Proc Natl Acad Sci U S A
; 112(43): 13161-6, 2015 Oct 27.
Artículo
en Inglés
| MEDLINE
| ID: mdl-26443859
RESUMEN
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.