Counting problems arise in many different fields, e.g., statistical physics, economics and machine learning. In order to study the complexity of counting problems, several natural frameworks have been proposed. Two well studied frameworks are counting constraint satisfaction problems (#CSP) and Holant problems. For counting satisfaction problems over the Boolean domain, two explicit tractable families namely and , are identified; any function set which is not contained in these two families is proved to be #P-hard. Furthermore, counting CSPd is the counting constraint satisfaction problem restricted to the instances where every variable occurs a multiple of d times. The team not only generalized local affine functions to #CSPd for general d, but also gives new tractable classes by combining local holographic transformations with global holographic transformation. Moreover, the team showed how to use local holographic transformations to prove hardness. This is of independent interests in the complexity classification of counting problems.
Recently, significant progresses have been made in the complexity classification of counting problems for three frameworks, graph homomorphisms, the counting constraint satisfaction problems and Holant problems. Holographic transformations played a key role in this project. In order to apply a holographic transformation on a particular situation, a research team led by Zhiguo FU published their new research on 27 March 2023 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
In the past twenty years, a series of remarkable complexity dichotomy theorems were built for counting problems. The key techniques to prove hardness were gadget constructions, interpolation and holographic transformations.
The team gives an example which is #P-hard by introducing local holographic transformations as a new tool to prove hardness. Specially, local affine functions partially reflect the difficulty in proving a Holant problem: Nice structures hide in strange supports and we have no powerful tools. Overall, there is still a long way to go to achieve a complete complexity classification for Holant problems with complex-valued and asymmetric signatures.
