{"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":1789015905220,"version":"build-2803163510"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>For certain subclasses of NP, $\\oplus$P, or #P characterized by local constraints, it is known that if there exist any problems within that subclass that are not polynomial time computable, then all the problems in the subclass are NP-complete, $\\oplus$P-complete, or #P-complete. Such dichotomy results have been proved for characterizations such as constraint satisfaction problems and directed and undirected graph homomorphism problems, often with additional restrictions. Here we give a dichotomy result for the more expressive framework of Holant problems. For example, these additionally allow for the expression of matching problems, which have had pivotal roles in the development of complexity theory. As our main result we prove the dichotomy theorem that, for the class $\\oplus$P, every set of symmetric Holant signatures of any arities that is not polynomial time computable is $\\oplus$P-complete. The result exploits some special properties of the class $\\oplus$P and characterizes four distinct tractable subclasses within $\\oplus$P. It leaves open the corresponding questions for NP, $\\#$P, and $\\#_k$P for $k\\neq 2$.<\/jats:p>","DOI":"10.1137\/100815530","type":"journal-article","created":{"date-parts":[[2013,2,14]],"date-time":"2013-02-14T16:34:55Z","timestamp":1360859695000},"page":"324-356","source":"Crossref","is-referenced-by-count":25,"title":["The Complexity of Symmetric Boolean Parity Holant Problems"],"prefix":"10.1137","volume":"42","author":[{"given":"Heng","family":"Guo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leslie G.","family":"Valiant","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,2,14]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.02.002"},{"key":"atypb2","first-page":"203","author":"Beigel R.","year":"1998","journal-title":"New York"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"R. A. Brualdi and H. J. Ryser,\n                      Combinatorial Matrix Theory\n                      , Cambridge University Press, Cambridge, UK, 1991.","DOI":"10.1017\/CBO9781107325708"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"A. A. Bulatov,\n                      The complexity of the counting constraint satisfaction problem\n                      , in ICALP '08: Proceedings of the 35th International Colloquium on Automata, Languages, and Programming, Part I, L. Aceto, I. Damg\\aard, L. A. Goldberg, M. M. Halld\u00f3rsson, A. Ing\u00f3lfsd\u00f3ttir, and I. Walukiewicz, eds., Lect. Notes Comput. Sci. 5125, Springer-Verlag, Berlin, 2008, pp. 646-661.","DOI":"10.1007\/978-3-540-70575-8_53"},{"key":"atypb6","first-page":"562","author":"Bulatov A. A.","year":"2003","journal-title":"NJ"},{"key":"atypb7","first-page":"275","author":"Cai J.-Y.","year":"2010","journal-title":"Berlin"},{"key":"atypb8","first-page":"305","author":"Cai J.-Y.","year":"2007","journal-title":"Washington, DC"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, H. Guo, and T. Williams,\n                      A Complete Dichotomy Rises from the Capture of Vanishing Signatures\n                      , preprint, arXiv:1204.6445, 2012.","DOI":"10.1145\/2488608.2488687"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"J.Y. Cai, S. Huang, and P. Lu,\n                      From Holant to \\#CSP and Back: Dichotomy for Holant$^c$ Problems\n                      , preprint, arXiv:1004.0803, 2010.","DOI":"10.1007\/978-3-642-17517-6_24"},{"key":"atypb11","first-page":"401","author":"Cai J.-Y.","year":"2007","journal-title":"New York"},{"key":"atypb12","first-page":"568","author":"Cai J.-Y.","year":"2008","journal-title":"New York"},{"key":"atypb13","first-page":"644","author":"Cai J.-Y.","year":"2008","journal-title":"Washington, DC"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.10.039"},{"key":"atypb15","first-page":"715","author":"Cai J.-Y.","year":"2009","journal-title":"New York"},{"key":"atypb16","first-page":"427","author":"Cai J.-Y.","year":"2010","journal-title":"NJ"},{"key":"atypb17","first-page":"38","volume":"1854","author":"Cayley A.","journal-title":"Crelle's J."},{"key":"atypb18","unstructured":"M. Cook and J. Bruck,\n                      Implementability Among Predicates\n                      , Tech. report, California Institute of Technology, Pasadena, CA, 2005."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90068-8"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0016"},{"key":"atypb21","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. 7, SIAM, Philadelphia, 2001.","DOI":"10.1137\/1.9780898718546"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"C. T. J. Dodson and T. Poston,\n                      Tensor Geometry\n                      , Grad. Texts in Math. 130, Springer-Verlag, New York, 1991.","DOI":"10.1007\/978-3-642-10514-2"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/070690201"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314691"},{"key":"atypb25","unstructured":"J. Faben,\n                      The Complexity of Counting Solutions to Generalised Satisfiability Problems Modulo k\n                      , preprint, arXiv:0809.1836, 2008."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/090757496"},{"key":"atypb28","first-page":"249","author":"Guo H.","year":"2011","journal-title":"Germany"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"H. Guo, P. Lu, and L. G. Valiant,\n                      The complexity of symmetric boolean parity Holant problems (extended abstract)\n                      , in Proceedings of the 38th International Colloquium Conference on Automata, Languages, and Programming, L. Aceto, M. Henzinger, and J. Sgall, eds., Lect. Notes Comput. Sci. 6755, Springer-Verlag, Berlin, 2011, pp. 712-723.","DOI":"10.1007\/978-3-642-22006-7_60"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"S. Huang and P. Lu,\n                      A Dichotomy for Real Weighted Holant Problems\n                      , manuscript, 2011.","DOI":"10.1109\/CCC.2012.16"},{"key":"atypb31","unstructured":"M. Kowalczyk and J.Y. Cai,\n                      Holant problems for regular graphs with complex edge functions\n                      , in Proceedings of the 27th Annual Symposium on Theoretical Aspects of Computer Science, LIPIcs 5, J.Y. Marion and T. Schwentick, eds., Schloss Dagstuhl, Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany, 2010, pp. 525-536."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/BF01889919"},{"key":"atypb34","first-page":"269","author":"Papadimitriou C. H.","year":"1982","journal-title":"London"},{"key":"atypb35","first-page":"216","author":"Schaefer T. J.","year":"1978","journal-title":"New York"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/0221023"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00325-5"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700377025"},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"L. G. Valiant,\n                      Holographic algorithms (extended abstract)\n                      , in FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Washington, DC, 2004, pp. 306-315.","DOI":"10.1109\/FOCS.2004.34"},{"key":"atypb41","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, IEEE Computer Society Press, Washington, DC, 2006, pp. 509-517.","DOI":"10.1109\/FOCS.2006.7"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1137\/070682575"},{"key":"atypb43","first-page":"577","author":"Valiant L. G.","year":"2010","journal-title":"Berlin"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90135-0"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100815530","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:30Z","timestamp":1787335950000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100815530"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/100815530"],"URL":"https:\/\/doi.org\/10.1137\/100815530","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}