← All papers
First page of A Dichotomy for Complex Boolean Holant with Binary Disequality

A Dichotomy for Complex Boolean Holant with Binary Disequality

Chenghua Liu, Boning Meng

cs.CC Aug 31, 2026 · v2
The full dichotomy proof is formalized in Lean, with public statements, proofs, exact certificates, and a Comparator-based challenge file; corrections were verified in Lean.
We classify Boolean Holant problems with a supplied binary disequality signature and an arbitrary fixed finite set of algebraic complex-valued signatures. Each problem is polynomial-time computable or $\#\mathsf{P}$-hard, and the tractability criterion is decidable. The proof combines arity reduction with the growth of the available binary transfer group and uses stable pairs to recover the structure of higher-arity signatures. We also prove a dichotomy for the disequality-edge model when the signature set contains an endpoint-nondegenerate irreducible eight-vertex signature, resolving the corresponding arity-four cases in the main proof.

The goal is to classify the complexity of Boolean Holant problems that come with a supplied binary disequality signature and an arbitrary finite set of algebraic complex-valued signatures. Each such problem should be shown to be either polynomial-time computable or #P-hard, with a decidable criterion separating the two.

The proof combines arity reduction with tracking how the group of available binary transfers grows. This group is a finite subgroup of PGL2(C): cyclic, dihedral, or Platonic. Stable pairs and comparisons of self-loop contractions are used to reconstruct higher-arity signatures. An eight-vertex dichotomy handles the arity-four cases, and the whole proof is formalized in Lean with exact finite certificates.

Every problem is shown to be either in P or #P-hard, and the tractability criterion is decidable. A dichotomy is also proved for the disequality-edge model containing an endpoint-nondegenerate irreducible eight-vertex signature. The Lean formalization led to two corrections of the original arXiv version.