A Dichotomy for Complex Boolean Holant with Binary Disequality

摘要

We prove a complexity dichotomy for Boolean Holant problems defined by arbitrary finite sets of algebraic complex-valued signatures when binary disequality is available. The tractable cases are characterized by an explicit, decidable criterion.