A Full Complexity Dichotomy for Complex-Valued Boolean Holant Problems
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.
