{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T14:28:33Z","timestamp":1789136913721,"version":"build-2803163510"},"reference-count":17,"publisher":"National Academy of Sciences","issue":"43","license":[{"start":{"date-parts":[[2016,4,6]],"date-time":"2016-04-06T00:00:00Z","timestamp":1459900800000},"content-version":"vor","delay-in-days":183,"URL":"http:\/\/www.pnas.org\/site\/misc\/userlicense.xhtml"}],"funder":[{"DOI":"10.13039\/501100000781","name":"EC | European Research Council","doi-asserted-by":"publisher","award":["FP7\/2007-2013"],"award-info":[{"award-number":["FP7\/2007-2013"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2015,10,27]]},"abstract":"<jats:title>Significance<\/jats:title>\n                  <jats:p>\n                    Spin systems are a primary object of study in statistical physics. Computational complexity is the rigorous study of the computational resources required to achieve specified computational goals. We examine the problem of estimating the partition function of a\n                    <jats:italic>q<\/jats:italic>\n                    -state spin system from the point of view of computational complexity. There are just three possible levels of computational difficulty, depending on the interaction strengths between adjacent spins. Every nontrivial\n                    <jats:italic>q<\/jats:italic>\n                    -state spin system, irrespective of the number\n                    <jats:italic>q<\/jats:italic>\n                    of spins, is computationally equivalent to one of two fundamental two-state spin systems. We give a simple characterization of the classification.\n                  <\/jats:p>","DOI":"10.1073\/pnas.1505664112","type":"journal-article","created":{"date-parts":[[2015,10,6]],"date-time":"2015-10-06T22:08:29Z","timestamp":1444169309000},"page":"13161-13166","update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":16,"title":["A complexity classification of spin systems with an external field"],"prefix":"10.1073","volume":"112","author":[{"given":"Leslie Ann","family":"Goldberg","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford OX1 3QD, United Kingdom;"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"341","published-online":{"date-parts":[[2015,10,6]]},"reference":[{"key":"e_1_3_3_1_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.06.006"},{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830600767X"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_3_3_5_2","first-page":"45","volume-title":"Proceedings of the 26th Annual IEEE Conference on Computational Complexity","author":"Cai J","year":"2011","unstructured":"J Cai, X Chen, P Lu, Non-negatively weighted #CSP: An effective complexity dichotomy. Proceedings of the 26th Annual IEEE Conference on Computational Complexity (IEEE, New York), pp. 45\u201354 (2011)."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450146"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_3_3_8_2","first-page":"39","article-title":"Ein kombinatorischer Satz","volume":"7","author":"R\u00e9dei L","year":"1934","unstructured":"L R\u00e9dei, Ein kombinatorischer Satz. Acta Litt. Sci. Szeged 7, 39\u201343, German. (1934).","journal-title":"Acta Litt. Sci. Szeged"},{"key":"e_1_3_3_9_2","volume-title":"Graph Theory, Graduate Texts in Mathematics","author":"Bondy JA","year":"2008","unstructured":"JA Bondy, USR Murty Graph Theory, Graduate Texts in Mathematics (Springer, New York) Vol 244 (2008)."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.03.015"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01415751"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2528401"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10090"},{"key":"e_1_3_3_16_2","first-page":"67","volume-title":"Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Li L","year":"2013","unstructured":"L Li, P Lu, Y Yin, Correlation decay up to uniqueness in spin systems. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, Philadelphia), pp. 67\u201384 (2013)."},{"key":"e_1_3_3_17_2","first-page":"843","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Liu J","year":"2014","unstructured":"J Liu, P Lu, C Zhang, The complexity of ferromagnetic two-spin systems with external fields. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Leibniz-Zentrum f\u00fcr Informatik GmbH, Wadern, Germany), pp. 843\u2013856 (2014)."}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.pnas.org\/syndication\/doi\/10.1073\/pnas.1505664112","content-type":"unspecified","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.1505664112","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,12]],"date-time":"2022-04-12T23:45:47Z","timestamp":1649807147000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/full\/10.1073\/pnas.1505664112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,6]]},"references-count":17,"journal-issue":{"issue":"43","published-print":{"date-parts":[[2015,10,27]]}},"alternative-id":["10.1073\/pnas.1505664112"],"URL":"https:\/\/doi.org\/10.1073\/pnas.1505664112","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10,6]]},"assertion":[{"value":"2015-10-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}