A Complete Dichotomy Rises from the Capture of Vanishing Signatures
Jin‐Yi Cai, Heng Guo, Tyson Williams · SIAM Journal on Computing · 2016
We prove a complexity dichotomy theorem for Holant problems over an arbitrary set of complex-valued symmetric constraint functions $\mathcal{F}$ on Boolean variables. This extends and unifies all previous dichotomies for Holant problems on symmetric constraint functions (taking values without a finite modulus). We define and characterize all symmetric vanishing signatures; they turn out to be essential to the complete classification of Holant problems. The dichotomy theorem has an explicit tractability criterion expressible in terms of holographic transformations. A Holant problem defined by a set of constraint functions $\mathcal{F}$ is solvable in polynomial time if it satisfies this tractability criterion, and is #P-hard otherwise. The tractability criterion can be intuitively stated as follows: A set $\mathcal{F}$ is tractable if (1) every function in $\mathcal{F}$ has arity at most two; or (2) $\mathcal{F}$ is transformable to an affine type; or (3) $\mathcal{F}$ is transformable to a product type; or (4) $\mathcal{F}$ is vanishing, combined with the right type of binary functions; or (5) $\mathcal{F}$ belongs to a special category of vanishing-type Fibonacci gates. The proof of this theorem utilizes many previous dichotomy theorems on Holant problems and Boolean constraint satisfaction problems (#CSP). Holographic transformations play an indispensable role as both a proof technique and in the statement of the tractability criterion.