2026-07-21T12:18:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7384 2024-03-06T10:40:19Z ddc:004 open_access

The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights Lin, Jiabao Wang, Hanpin counting complexity dichotomy Holant #CSP Holant problem is a general framework to study the computational complexity of counting problems. We prove a complexity dichotomy theorem for Holant problems over the Boolean domain with non-negative weights. It is the first complete Holant dichotomy where constraint functions are not necessarily symmetric. Holant problems are indeed read-twice #CSPs. Intuitively, some #CSPs that are #P-hard become tractable when restricted to read-twice instances. To capture them, we introduce the Block-rank-one condition. It turns out that the condition leads to a clear separation. If a function set F satisfies the condition, then F is of affine type or product type. Otherwise (a) Holant(F) is #P-hard; or (b) every function in F is a tensor product of functions of arity at most 2; or (c) F is transformable to a product type by some real orthogonal matrix. Holographic transformations play an important role in both the hardness proof and the characterization of tractability. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jiabao Lin and Hanpin Wang 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.29 urn:nbn:de:0030-drops-73846 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.29 eng https://creativecommons.org/licenses/by/3.0/legalcode