A complexity classification of spin systems with an external field

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) equ...

Descrizione completa

Dettagli Bibliografici
Autori principali: Goldberg, L, Jerrum, M
Natura: Journal article
Pubblicazione: National Academy of Sciences 2015