Holant problems with four-variable signatures get complexity classification
The Computational Complexity of Holant Problems on 4-regular Graphs from the Stable Subgroup Sequence of $SL(2,\mathbb{C})$
Computational Complexity
Summary
Counting certain configurations in networks is a hard problem studied in computer science. The paper focuses on a specific type of such problems called Holant problems that use complex numbers and involve four inputs at each point. The authors solved a key open case by classifying these problems as either easy or hard to compute. They did this by introducing new mathematical tools from group theory, which helps in understanding the problem structure better.
What this means in practice
- •For algorithm designers: Create algorithms with better guarantees by knowing which Holant problems are feasible or infeasible for complex-valued inputs.
- •For complexity analysts: Use the complexity dichotomy to classify new counting problems arising in physics or network analysis with complex weights.
A theory result. No direct application yet.
Authors
Yuan Huang, Zhiguo Fu
Abstract
The Holant framework provides a general setting for studying counting problems and includes graph homomorphisms (\#GH) and counting constraint satisfaction problems (\#CSP) as special cases. Over the past twenty years, a series of computational complexity dichotomies have been established for Holant problems, but the classification for complex-valued signatures is still open. The main obstacle is the case in which all signatures have even arity. In this paper, we establish a dichotomy for Holant problems with a complex-valued 4-ary signature, which is a key base case for the full classification of Holant problems. We present a new strategy by introducing Schur's theorem, the classification of finite subgroups of $\mathrm{SL}(2,\mathbb{C})$ and stable subgroup sequences into the proof. These new techniques are of independent interest.