2017/02/09 by Jin-Yi Cai, Jin‐Yi Cai, Cai, Jin-Yi +4
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1702.02693
arxiv created 2017/02/09 · openalex publication_date 2017/02/09 · arxiv updated 2017/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Holant problems capture a class of Sum-of-Product computations such as counting matchings. It is inspired by holographic algorithms and is equivalent to tensor networks, with counting CSP being a special case. A classification for Holant problems is more difficult to prove, not only because it implies a classification for counting CSP, but also due to the deeper reason that there exist more intricate polynomial time tractable problems in the broader framework. We discover a new family of constraint functions \mathscrL which define polynomial time computable counting problems. These do not appear in counting CSP, and no newly discovered tractable constraints can be symmetric. It has a delicate support structure related to error-correcting codes. Local holographic transformations is fundamental in its tractability. We prove a complexity dichotomy theorem for all Holant problems defined by any real valued constraint function set on Boolean variables and contains two 0-1 pinning functions. Previously, dichotomy for the same framework was only known for symmetric constraint functions. he set \mathscrL supplies the last piece of tractability. We also prove a dichotomy for a variant of counting CSP as a technical component toward this Holant dichotomy.