Equivalence and Isomorphism for Boolean Constraint Satisfaction
| dc.creator | Boehler, E. | |
| dc.creator | Hemaspaandra, E. | |
| dc.creator | Reith, Steffen | |
| dc.creator | Vollmer, Heribert | |
| dc.date | 2002-02-25 | |
| dc.date.accessioned | 2026-07-07T03:18:10Z | |
| dc.date.available | 2026-07-07T03:18:10Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0202036 | |
| dc.identifier | http://arxiv.org/abs/cs/0202036 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31006 | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic in Computer Science | |
| dc.subject | F.4.1; F.2.2 | |
| dc.title | Equivalence and Isomorphism for Boolean Constraint Satisfaction | |
| dc.type | text |