Complexity classification found for Holant problems with three values
Group Action and Spin Representation Lead to a Holant* Complexity Dichotomy on Domain Size 3
Computational Complexity
Summary
This paper figures out when a certain type of mathematical problem called a Holant* problem can be solved quickly or is very hard, when the problem involves three possible values. The authors discovered a clear rule to decide which problems are easy and which are hard. To do this, they used advanced math involving group actions and special transformations called spin representations. Their work uncovers hidden structures in complex-valued problems that were not seen before and introduces new tools to analyze these problems systematically.
What this means in practice
- •For complexity theorists: Use the dichotomy to know exactly which Holant* problems on three values can be solved efficiently versus those that are computationally infeasible.
- •For algorithm designers: Guide the design of algorithms by identifying tractable cases in problems involving complex-valued constraints on three-element domains.
A theory result. No direct application yet.
Authors
Jin-Yi Cai, Jin Soo Ihm
Abstract
We prove a complexity dichotomy theorem for $\mathrm{Holant}^*$ problems over complex-valued symmetric constraint functions $\mathcal{F}$ on domain size $3$. We give a decidable tractability criterion and prove that if $\mathcal{F}$ satisfies the criterion, then $\mathrm{Holant}^*(\mathcal{F})$ is solvable in polynomial time, and otherwise it is #P-hard. This is the first Holant dichotomy for a set of complex-valued constraint functions on higher domains. We show that complex-valued constraint functions have a rich structure not observed in real-valued constraint functions. This structure is only revealed when we analyze them in a bipartite Holant setting with a non-standard bilinear form and provides the backbone to the proof of the dichotomy. We use group actions and the spin representation of $\mathrm{SL}(2, \mathbb{C})$ in $\mathrm{SO}(3, \mathbb{C})$ and the generalized orthogonal group to facilitate this analysis. We also introduce $\textit{frames}$ and $\textit{shells}$. Frames linearize the group action and provide a unified framework for proving #P-hardness when used in conjunction with shells. Furthermore, we characterize the lower dimensional constraint functions by $\textit{annihilators}$, which makes it possible to analyze $\textit{essentially Boolean domain}$ functions in domain size $3$.