On the equivalence of constraint satisfaction problems

Abstract

A solution of a Constraint Satisfaction Problem (CSP) is an assignment of values to all its variables such that all its constraints are satisfied. Usually two CSPs are considered equivalent if they have the same solution set. We find this definition limiting, and develop a more general definition based on the concept of mutual reducibility. In this extended scheme it is reasonable to consider a pair of CSPs equivalent even if they have different solutions. The basic idea behind the extended scheme is that two CSPs can be considered equivalent whenever they contain the same "amount of information", i.e. whenever it is possible to obtain the solution of one of them from the solution of the other one, and viceversa. In this way, both constraint and variable redundancy are allowed in CSPs belonging to the same equivalence class. As an example of the usefulness of this new notion of equivalence, we formally prove that binary and non-binary CSPs are equivalent (in the new sense). Such a pro...