2026-07-20T11:02:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23717 2025-10-27T10:42:46Z ddc:004 open_access

From an Odd Arity Signature to a Holant Dichotomy Meng, Boning Wang, Juqiu Xia, Mingji Zheng, Jiayi Complexity dichotomy Counting Holant problem #P Holant is an essential framework in the field of counting complexity. For over fifteen years, researchers have been clarifying the complexity classification for complex-valued Holant on Boolean domain, a challenge that remains unresolved. In this article, we prove a complexity dichotomy for complex-valued Holant on Boolean domain when a non-trivial signature of odd arity exists. This dichotomy is based on the dichotomy for #EO, and consequently is an FP^NP vs. #P dichotomy as well, stating that each problem is either in FP^NP or #P-hard. Furthermore, we establish a generalized version of the decomposition lemma for complex-valued Holant on Boolean domain. It asserts that each signature can be derived from its tensor product with other signatures, or conversely, the problem itself is in FP^NP. We believe that this result is a powerful method for building reductions in complex-valued Holant, as it is also employed as a pivotal technique in the proof of the aforementioned dichotomy in this article. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Boning Meng and Juqiu Wang and Mingji Xia and Jiayi Zheng 2025 Is Part Of LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2025.23 urn:nbn:de:0030-drops-237177 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.23 eng https://creativecommons.org/licenses/by/4.0/legalcode