arXiv:2609.00219 · v2

A Dichotomy for Complex Boolean Holant with Binary Disequality

首次提交 2026-09-01 02:29

版本更新 2026-11-06 23:16

雷达观测 2026-11-09 13:22

摘要

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.

作者备注：242 pages; proof and exposition revised, corrections made, Lean repository linked