A Dichotomy for Complex Boolean Holant with Binary Disequality
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.
