Equivalence and Isomorphism for Boolean Constraint Satisfaction

Details Equivalence and Isomorphism for Boolean Constraint Satisfaction Equivalence and Isomorphism for Boolean Constraint Satisfaction

2002-02-25

arxiv.org/abs/cs/0202036v1

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Equivalence and Isomorphism for Boolean Constraint Satisfaction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Equivalence and Isomorphism for Boolean Constraint Satisfaction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Equivalence and Isomorphism for Boolean Constraint Satisfaction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-358810