Equivalence and Isomorphism for Boolean Constraint Satisfaction
<|reference_start|>Equivalence and Isomorphism for Boolean Constraint Satisfaction: A Boolean constraint satisfaction instance is a conjunction of constraint applications, where the allowed constraints are drawn from a fixed set B of Boolean functions. We consider the problem of determining whether two given constraint satisfaction instances are equivalent and prove a Dichotomy Theorem by showing that for all sets C of allowed constraints, this problem is either polynomial-time solvable or coNP-complete, and we give a simple criterion to determine which case holds.   A more general problem addressed in this paper is the isomorphism problem, the problem of determining whether there exists a renaming of the variables that makes two given constraint satisfaction instances equivalent in the above sense. We prove that this problem is coNP-hard if the corresponding equivalence problem is coNP-hard, and polynomial-time many-one reducible to the graph isomorphism problem in all other cases.<|reference_end|>
@article{boehler2002equivalence,
    title={Equivalence and Isomorphism for Boolean Constraint Satisfaction},
    author={E. Boehler, E. Hemaspaandra, Steffen Reith, Heribert Vollmer},
    journal={arXiv preprint arXiv:cs/0202036},
    year={2002},
    archivePrefix={arXiv},
    eprint={cs/0202036},
    primaryClass={cs.CC cs.LO}
}