A Dichotomy for Complex Boolean Holant with Binary DisequalityResearch Paper
Many counting problems ask for a sum, over all assignments of bits, of a product of local weights. A complexity dichotomy sorts every choice of local weights into two classes: those for which the sum can be computed in polynomial time, and those for which computing it is #P-hard. For Boolean counting constraint satisfaction such dichotomies are known for…