2026-07-22T06:25:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9016 2024-03-06T10:43:09Z ddc:004 open_access

A Complete Dichotomy for Complex-Valued Holant^c Backens, Miriam computational complexity counting complexity Holant problems dichotomy entanglement Holant problems are a family of counting problems on graphs, parametrised by sets of complex-valued functions of Boolean inputs. Holant^c denotes a subfamily of those problems, where any function set considered must contain the two unary functions pinning inputs to values 0 or 1. The complexity classification of Holant problems usually takes the form of dichotomy theorems, showing that for any set of functions in the family, the problem is either #P-hard or it can be solved in polynomial time. Previous such results include a dichotomy for real-valued Holant^c and one for Holant^c with complex symmetric functions, i.e. functions which only depend on the Hamming weight of the input. Here, we derive a dichotomy theorem for Holant^c with complex-valued, not necessarily symmetric functions. The tractable cases are the complex-valued generalisations of the tractable cases of the real-valued Holant^c dichotomy. The proof uses results from quantum information theory, particularly about entanglement. This full dichotomy for Holant^c answers a question that has been open for almost a decade. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Miriam Backens 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.12 urn:nbn:de:0030-drops-90168 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.12 eng https://creativecommons.org/licenses/by/3.0/legalcode