{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:10Z","timestamp":1787340370477,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>Partition functions, also known as homomorphism functions, form a rich family of graph invariants that contain combinatorial invariants such as the number of k-colorings or the number of independent sets of a graph and also the partition functions of certain \u201cspin glass\u201d models of statistical physics such as the Ising model. Building on earlier work by Dyer and Greenhill [Random Structures Algorithms, 17 (2000), pp. 260\u2013289] and Bulatov and Grohe [Theoret. Comput. Sci., 348 (2005), pp. 148\u2013186], we completely classify the computational complexity of partition functions. Our main result is a dichotomy theorem stating that every partition function is either computable in polynomial time or #P-complete. Partition functions are described by symmetric matrices with real entries, and we prove that it is decidable in polynomial time in terms of the matrix whether a given partition function is in polynomial time or #P-complete. While in general it is very complicated to give an explicit algebraic or combinatorial description of the tractable cases, for partition functions described by Hadamard matrices (these turn out to be central in our proofs) we obtain a simple algebraic tractability criterion, which says that the tractable cases are those \u201crepresentable\u201d by a quadratic polynomial over the field $\\mathbb{F}_2$.<\/jats:p>","DOI":"10.1137\/090757496","type":"journal-article","created":{"date-parts":[[2010,8,5]],"date-time":"2010-08-05T18:13:42Z","timestamp":1281032022000},"page":"3336-3402","source":"Crossref","is-referenced-by-count":66,"title":["A Complexity Dichotomy for Partition Functions with Mixed Signs"],"prefix":"10.1137","volume":"39","author":[{"given":"Leslie Ann","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marc","family":"Thurley","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,8,5]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"L. Barto, M. Kozik, and T. Niven,\n                      Graphs, polymorphisms and the complexity of homomorphism problems\n                      , in STOC '08: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, ACM, New York, 2008, pp. 789\u2013796.","DOI":"10.1145\/1374376.1374488"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Bl\u00e4ser and H. Dell,\n                      Complexity of the cover polynomial\n                      , in Proceedings of the 34th International Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 4596, L. Arge, Ch. Cachin, T. Jurdzinski, and A. Tarlecki, eds., Springer-Verlag, New York, 2007, pp. 801\u2013812.","DOI":"10.1007\/978-3-540-73420-8_69"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. Bulatov,\n                      The complexity of the counting constraint satisfaction problem\n                      , in Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 5125, Springer-Verlag, New York, 2008, pp. 646\u2013661.","DOI":"10.1007\/978-3-540-70575-8_53"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"A. Bulatov and V. Dalmau,\n                      Towards a dichotomy theorem for the counting constraint satisfaction problem\n                      , in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 2003, pp. 562\u2013571.","DOI":"10.1109\/SFCS.2003.1238229"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, X. Chen, and P. Lu,\n                      Graph homomorphisms with complex values: A dichotomy theorem\n                      , in Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP '10), Lecture Notes in Comput. Sci. 6198, Springer-Verlag, New York, 2010, pp. 275\u2013286.","DOI":"10.1007\/978-3-642-14165-2_24"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"key":"R9","unstructured":"M. Dyer, L. A. Goldberg, and M. Jerrum,\n                      A complexity dichotomy for hypergraph partition functions\n                      , J. Computational Complexity, to appear."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314691"},{"key":"R11","unstructured":"A. Ehrenfeucht and M. Karpinski,\n                      The Computational Complexity of (xor, and)-Counting Problems\n                      , Tech. Report 8543-CS, available at http:\/\/citeseer.ist.psu.edu\/ehrenfeucht90computational.html, 1990."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-06-00529-7"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"L. A. Goldberg, S. Kelk, and M. Paterson,\n                      \n                        The complexity of choosing an\n                        H\n                        -colouring (nearly) uniformly at random\n                      \n                      , in Proceedings of the 34th ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 53\u201362.","DOI":"10.1145\/509907.509917"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"L. A. Goldberg and M. Jerrum,\n                      Inapproximability of the Tutte polynomial\n                      , in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 459\u2013468.","DOI":"10.1145\/1250790.1250858"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100068936"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"R18","unstructured":"R. Lidl and H. Niederreiter,\n                      Finite Fields\n                      , 2nd ed., Encyclopedia Math. Appl. 20, Cambridge University Press, Cambridge, UK, 1997."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-8858(03)00087-3"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.04.012"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.11.008"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"A. Sokal,\n                      The multivariate Tutte polynomial\n                      , in Surveys in Combinatorics, Cambridge University Press, Cambridge, UK, 2005, pp. 173\u2013226.","DOI":"10.1017\/CBO9780511734885.009"},{"key":"R23","unstructured":"M. Thurley,\n                      The Complexity of Partition Functions\n                      , Ph.D. thesis, Humboldt-Universit\u00e4t zu Berlin, Berlin, 2009."},{"key":"R24","doi-asserted-by":"crossref","unstructured":"D. J. A. Welsh,\n                      Complexity: Knots, Colourings and Counting\n                      , London Math. Soc. Lecture Note Ser. 186, Cambridge University Press, Cambridge, UK, 1993.","DOI":"10.1017\/CBO9780511752506"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090757496","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:32:10Z","timestamp":1787337130000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090757496"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":24,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090757496"],"URL":"https:\/\/doi.org\/10.1137\/090757496","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}