← All papers
First page of A Full Complexity Dichotomy for Complex-Valued Boolean Holant Problems

A Full Complexity Dichotomy for Complex-Valued Boolean Holant Problems

Chenghua Liu, Boning Meng, Juqiu Wang

cs.CC Sep 6, 2026 · v2
The authors report completing a Lean formalization of the complexity dichotomy proof for Boolean Holant problems, with AI assistance.
A Boolean Holant problem evaluates a graph partition function specified by local signatures at its vertices. We prove a complexity dichotomy for arbitrary finite sets of algebraic complex-valued signatures on general graphs: an explicit, decidable criterion characterizes the polynomial-time cases, and every remaining case is $\#\mathsf{P}$-hard under polynomial-time Turing reductions. The proof resolves the all-even case by constructing signatures with nonzero endpoints and all remaining support on the central layer, then classifying them according to half their arity. Binary transfer groups and matching-product reconstruction provide the main tools in the small- and large-height cases, respectively.

The goal is to classify the computational complexity of Boolean Holant problems for arbitrary finite sets of algebraic complex-valued signatures on general graphs. The open case was sets made up entirely of even-arity signatures, with no symmetry restriction and no prescribed auxiliary binary signature.

A holographic transformation moves the problem into K-coordinates. Odd-arity cases are then handed off to existing dichotomies. For the all-even case, a 'mountain' signature is simulated: it has nonzero endpoint values and all other support on the central Hamming layer, and it is classified by its height (half its arity). Height one is handled with binary transfer groups and contractions. Higher heights use local EO constructions and matching-product reconstruction. The authors state that the proof was formalized in Lean.

Every case either satisfies an explicit, decidable tractability criterion and is polynomial-time computable, or is #P-hard under polynomial-time Turing reductions. This gives a full dichotomy for complex-valued Boolean Holant problems.