{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,10]],"date-time":"2026-09-10T04:51:41Z","timestamp":1789015901777,"version":"build-2803163510"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["0914969"],"award-info":[{"award-number":["0914969"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1217549"],"award-info":[{"award-number":["1217549"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1149257"],"award-info":[{"award-number":["1149257"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1423100"],"award-info":[{"award-number":["1423100"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>We prove a complexity dichotomy theorem for counting constraint satisfaction problems (#CSPs) with nonnegative and algebraic weights. This caps a long series of important results on counting problems including counting unweighted and weighted graph homomorphisms and the celebrated dichotomy theorem for unweighted #CSPs. Our dichotomy theorem gives a succinct criterion for tractability. If a set $\\mathcal{F}$ of constraint functions satisfies this criterion, then the problem #CSP$(\\mathcal{F})$ defined by $\\mathcal{F}$ is solvable in polynomial time; if $\\mathcal{F}$ does not satisfy this criterion, then the problem is #P-hard. Furthermore, we show that the question of whether a given $\\mathcal{F}$ satisfies the criterion or not is decidable in NP. Surprisingly, our tractability criterion is simpler than the previous criteria for the more restricted classes of counting problems, although when specialized to those classes, they are logically equivalent. Our proof mainly uses linear algebra and represents a departure from universal algebra, the dominant methodology in recent years for the study of #CSPs on large domains.<\/jats:p>","DOI":"10.1137\/15m1032314","type":"journal-article","created":{"date-parts":[[2016,12,20]],"date-time":"2016-12-20T10:40:14Z","timestamp":1482230414000},"page":"2177-2198","source":"Crossref","is-referenced-by-count":29,"title":["Nonnegative Weighted #CSP: An Effective Complexity Dichotomy"],"prefix":"10.1137","volume":"45","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xi","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,12,20]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0272-6"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/050628957"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.12.002"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"atypb5","first-page":"321","author":"Bulatov A. A.","year":"2003","journal-title":"Computer Science"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/2528400"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.09.005"},{"key":"atypb9","first-page":"183","author":"Bulatov A. A.","year":"2003","journal-title":"Heidelberg"},{"key":"atypb10","first-page":"68","author":"Bulatov A. A.","year":"2008","journal-title":"Heidelberg"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"S. Burris and H. P. Sankappanavar,\n                      A Course in Universal Algebra\n                      , Grad. Texts in Math. 78, Springer-Verlag, New York, Berlin, 1981.","DOI":"10.1007\/978-1-4613-8130-3"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"J.Y. Cai and X. Chen,\n                      A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights\n                      , in Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 437-446,https:\/\/doi.org\/10.1109\/FOCS.2010.49.","DOI":"10.1109\/FOCS.2010.49"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"J.Y. Cai and X. Chen,\n                      Complexity of counting CSP with complex weights\n                      , in Proceedings of the 44th Annual ACM Symposium on Theory of Computing, 2012, pp. 909-920,https:\/\/doi.org\/10.1145\/2213977.2214059.","DOI":"10.1145\/2213977.2214059"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, X. Chen, and P. Lu,\n                      Nonnegatively weighted #CSPs: An effective complexity dichotomy\n                      , in Proceedings of the 25th IEEE Conference on Computational Complexity, 2011, pp. 45-54.","DOI":"10.1109\/CCC.2011.32"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/110840194"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, Z. Fu, H. Guo, and T. Williams,\n                      A Holant dichotomy: Is the FKT algorithm universal?\n                      , in Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 2015, pp. 1259-1276,https:\/\/doi.org\/10.1109\/FOCS.2015.81.","DOI":"10.1109\/FOCS.2015.81"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/15M1049798"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, H. Guo, and T. Williams,\n                      The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems\n                      , in Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 2014, pp. 601-610,https:\/\/doi.org\/10.1109\/FOCS.2014.70.","DOI":"10.1109\/FOCS.2014.70"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9626-6"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, P. Lu, and M. Xia,\n                      Holant problems and counting CSP\n                      , in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 715-724,https:\/\/doi.org\/10.1145\/1536414.1536511.","DOI":"10.1145\/1536414.1536511"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, P. Lu, and M. Xia,\n                      Holographic algorithms with matchgates capture precisely tractable planar #CSP\n                      , in Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 427-436,https:\/\/doi.org\/10.1109\/FOCS.2010.48.","DOI":"10.1109\/FOCS.2010.48"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.132"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.93"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/07068062X"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314691"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/100811258"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"atypb29","unstructured":"R. Freese and R. McKenzie,\n                      Commutator Theory for Congruence Modular Varieties\n                      , Cambridge University Press, Cambridge, UK, 1987."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/090757496"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"D. Hobby and R. McKenzie,\n                      The Structure of Finite Algebras\n                      , Contemp. Math. 76, American Mathematical Society, Providence, RI, 1988,https:\/\/doi.org\/10.1090\/conm\/076.","DOI":"10.1090\/conm\/076"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00022-8"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2015.07.011"},{"key":"atypb38","first-page":"211","volume":"26","author":"Lenstra H. W.","year":"1992","journal-title":"S.)"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280291"},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"P. Raghavendra,\n                      Optimal algorithms and inapproximability results for every CSP?\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 245-254,https:\/\/doi.org\/10.1145\/1374376.1374414.","DOI":"10.1145\/1374376.1374414"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"P. Raghavendra and D. Steurer,\n                      How to round any CSP\n                      , in Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, pp. 586-594,https:\/\/doi.org\/10.1109\/FOCS.2009.74.","DOI":"10.1109\/FOCS.2009.74"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"T. J. Schaefer,\n                      The complexity of satisfiability problems\n                      , in Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978, pp. 216-226,https:\/\/doi.org\/10.1145\/800133.804350.","DOI":"10.1145\/800133.804350"},{"key":"atypb43","unstructured":"M. Thurley,\n                      The Complexity of Partition Functions on Hermitian Matrices\n                      , preprint,https:\/\/arxiv.org\/abs\/1004.0992, 2010."},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"M. Tulsiani,\n                      CSP gaps and reductions in the Lasserre hierarchy\n                      , in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 303-312,https:\/\/doi.org\/10.1145\/1536414.1536457.","DOI":"10.1145\/1536414.1536457"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1137\/070682575"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1032314","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:56:31Z","timestamp":1787338591000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1032314"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/15M1032314"],"URL":"https:\/\/doi.org\/10.1137\/15m1032314","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}