Equivalence Problems for Boolean Constraint Satisfaction

A Boolean constraint satisfaction instance is a conjunction of constraint applications, where the allowed constraints are drawn from a fi xed set C of Boolean functions. We consider the problem of determining whether two given constraint satisfaction instances are equivalent in the sense that they possess the same sets of satisfying assignments. We prove a Dichotomy Theorem by showing that for all…