A complexity classification of spin systems with an external field. (English) Zbl 1355.68120

Goldberg, Leslie Ann; Jerrum, Mark

Proc. Natl. Acad. Sci. USA 112, No. 43, 13161-13166 (2015).

Summary: 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.

MSC:

68Q25	Analysis of algorithms and problem complexity
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
82B20	Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics

References:

[1]	DOI: 10.1016/j.jcss.2014.06.006 · Zbl 1354.68114 · doi:10.1016/j.jcss.2014.06.006
[2]	DOI: 10.1007/s00453-003-1073-y · Zbl 1138.68424 · doi:10.1007/s00453-003-1073-y
[3]	DOI: 10.1017/S096354830600767X · Zbl 1170.82001 · doi:10.1017/S096354830600767X
[4]	DOI: 10.1016/0304-3975(86)90174-X · Zbl 0597.68056 · doi:10.1016/0304-3975(86)90174-X
[5]	Cai, Non-negatively weighted #CSP: An effective complexity dichotomy, in: Proceedings of the 26th Annual IEEE Conference on Computational Complexity pp 45– (2011)
[6]	Kolmogorov, The complexity of conservative valued csps, J Assoc Comput Mach 60 (2) pp 10– (2013) · Zbl 1281.68134 · doi:10.1145/2450142.2450146
[7]	Mitzenmacher, Probability and Computing (2005) · Zbl 1092.60001 · doi:10.1017/CBO9780511813603
[8]	Rédei, Ein kombinatorischer Satz, Acta Litt. Sci. Szeged 7 pp 39– (1934)
[9]	Bondy, Graph Theory, Graduate Texts in Mathematics Vol 244 (2008)
[10]	DOI: 10.1016/j.tcs.2008.03.015 · Zbl 1154.90011 · doi:10.1016/j.tcs.2008.03.015
[11]	DOI: 10.1007/BF01415751 · Zbl 0843.90101 · doi:10.1007/BF01415751
[12]	DOI: 10.1016/j.tcs.2005.09.011 · Zbl 1081.68030 · doi:10.1016/j.tcs.2005.09.011
[13]	Bulatov, The expressibility of functions on the Boolean domain, with applications to counting csps, J Assoc Comput Mach 60 (5) pp 32– (2013) · Zbl 1281.68131 · doi:10.1145/2528401
[14]	DOI: 10.1137/0222066 · Zbl 0782.05076 · doi:10.1137/0222066
[15]	DOI: 10.1002/rsa.10090 · Zbl 1030.82001 · doi:10.1002/rsa.10090
[16]	Li, Correlation decay up to uniqueness in spin systems, in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms pp 67– (2013) · doi:10.1137/1.9781611973105.5
[17]	Liu, The complexity of ferromagnetic two-spin systems with external fields, in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques pp 843– (2014)