{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,10]],"date-time":"2026-09-10T04:51:45Z","timestamp":1789015905245,"version":"build-2803163510"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant problems. Compared to counting constraint satisfaction problems (#CSP), it is a refinement with a more explicit role for the constraint functions. Both graph homomorphism and #CSP can be viewed as special cases of Holant problems. We prove complexity dichotomy theorems in this framework. Our dichotomy theorems apply to local constraint functions, which are symmetric functions on Boolean input variables and evaluate to arbitrary real or complex values. We discover surprising tractable subclasses of counting problems, which could not easily be specified in the #CSP framework. When all unary functions are assumed to be free ($\\mathrm{Holant}^*$ problems), the tractable ones consist of functions that are degenerate, or of arity at most two, or holographic transformations of Fibonacci gates. When only two special unary functions, the constant zero and constant one functions, are assumed to be free ($\\mathrm{Holant}^c$ problems), we further identify three special families of tractable cases. Then we prove that all other cases are #P-hard. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations.<\/jats:p>","DOI":"10.1137\/100814585","type":"journal-article","created":{"date-parts":[[2011,7,19]],"date-time":"2011-07-19T18:05:39Z","timestamp":1311098739000},"page":"1101-1132","source":"Crossref","is-referenced-by-count":39,"title":["Computational Complexity of Holant Problems"],"prefix":"10.1137","volume":"40","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mingji","family":"Xia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,7,19]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub, and S. Smale,\n                      Complexity and Real Computation\n                      , Springer-Verlag, New York, Secaucus, NJ, 1998.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"R3","unstructured":"A. A. Bulatov,\n                      The complexity of the counting constraint satisfaction problem\n                      , in Proc. ICALP (1), Lecture Notes in Computer Science 5125, L. Aceto, I. Damg\u00e5rd, L. A. Goldberg, M. M. Halld\u00f3rsson, A. Ing\u00f3lfsd\u00f3ttir, and I. Walukiewicz, eds., Springer, New York, 2008, pp. 646\u2013661."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. A. Bulatov and V. Dalmau,\n                      Towards a dichotomy theorem for the counting constraint satisfaction problem\n                      , in FOCS, IEEE Computer Society, New York, 2003, pp. 562\u2013571.","DOI":"10.1109\/SFCS.2003.1238229"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"A. A. Bulatov and M. Grohe,\n                      The complexity of partition functions\n                      , in Proc. ICALP, 2004, Turku, Finland, Lecture Notes in Comput. Sci. 3142, Springer, 2004, pp. 294\u2013306.","DOI":"10.1007\/978-3-540-27836-8_27"},{"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 Proc.  ICALP (1), 2010, Bordeaux, France, Lecture Notes in Comput. Sci. 6198, Springer, 2010, pp. 275\u2013286.","DOI":"10.1007\/978-3-642-14165-2_24"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.015"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.005"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9229-z"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, P. Lu, and M. Xia,\n                      Holant problems and counting CSP\n                      , in Proceedings of STOC 2009: The 41st Annual ACM Symposium on Theory of Computing, M. Mitzenmacher, ed., Bethesda, MD, pp. 715\u2013724, 2009.","DOI":"10.1145\/1536414.1536511"},{"key":"R12","unstructured":"J.Y. Cai, P. Lu, and M. Xia,\n                      Holographic algorithms by Fibonacci gates\n                      , Linear Algebra Appl. special issue on Tensors and Multilinear Algebra, to appear; available online from http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0024379511001625."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, P. Lu, and M. Xia,\n                      Holographic algorithms by Fibonacci gates and holographic reductions for hardness\n                      , in FOCS '08: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, PA, 2008, IEEE Computer Society, New York, 2008.","DOI":"10.1109\/FOCS.2008.34"},{"key":"R14","unstructured":"J.Y. Cai, P. Lu, and M. Xia,\n                      The complexity of complex weighted Boolean #CSP\n                      , Upcoming Journal Submission."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"N. Creignou, S. Khanna, and M. Sudan,\n                      Complexity classifications of Boolean constraint satisfaction problems\n                      , SIAM Monogr. Discrete Math. Appl., SIAM, Philadelphia, 2001.","DOI":"10.1137\/1.9780898718546"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90234-7"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"C. T. J. Dodson and T. Poston,\n                      Tensor geometry\n                      , Graduate Texts in Mathematics 130, Springer-Verlag, New York, 1991.","DOI":"10.1007\/978-3-642-10514-2"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/070690201"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"M. E. Dyer, L. A. Goldberg, and M. Paterson,\n                      On counting homomorphisms to directed acyclic graphs\n                      , in ICALP (1), Lecture Notes in Computer Science 4051, M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, eds., Springer, New York, 2006, pp. 38\u201349.","DOI":"10.1007\/11786986_5"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"M. E. Dyer, L. A. Goldberg, and M. Paterson,\n                      On counting homomorphisms to directed acyclic graphs\n                      , J. ACM, 54 (2007).","DOI":"10.1145\/1314690.1314691"},{"key":"R21","unstructured":"M. E. Dyer and C. S. Greenhill,\n                      The complexity of counting graph homomorphisms (extended abstract)\n                      , in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, San Francisco, CA, ACM\/SIAM, pp. 246\u2013255."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20036"},{"key":"R23","first-page":"37","volume":"20","author":"Freedman M.","year":"2007","journal-title":"J. AMS","ISSN":"https:\/\/id.crossref.org\/issn\/0771-1107","issn-type":"print"},{"key":"R24","unstructured":"L. A. Goldberg, M. Grohe, M. Jerrum, and M. Thurley,\n                      A complexity dichotomy for partition functions with mixed signs\n                      , CoRR, abs\/0804.1932, 2008."},{"key":"R25","first-page":"1209","volume":"27","author":"Kasteleyn P. W.","year":"1961","journal-title":"Phys."},{"key":"R26","unstructured":"P. W. Kasteleyn,\n                      Graph theory and crystal physics\n                      , in Graph Theory and Theoretical Physics, F. Harary, ed., Academic Press, London, 1967, pp. 43\u2013110."},{"key":"R27","unstructured":"K.I. Ko,\n                      Complexity theory of real functions\n                      , Birkh\u00e4user Boston, Cambridge, MA, 1991."},{"key":"R28","unstructured":"R. Lidl and H. Niederreiter,\n                      Finite fields\n                      , Encyclopedia of Mathematics and its Applications, Vol. 20, Cambridge University Press, Cambridge, 1997."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1080\/14786436108243366"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797321602"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700377025"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"L. G. Valiant,\n                      Accidental algorithms\n                      , in FOCS '06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC, 2006, IEEE Computer Society, pp. 509\u2013517.","DOI":"10.1109\/FOCS.2006.7"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/070682575"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.023"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100814585","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:26Z","timestamp":1787337266000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100814585"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100814585"],"URL":"https:\/\/doi.org\/10.1137\/100814585","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}