Exploiting Fixable, Removable, and Implied Values in Constraint Satisfaction Problems

摘要

Complete algorithms for constraint solving typically exploit properties like (in)consistency or interchangeability, which they detect by means of incomplete yet effective algorithms and use to reduce the search space. In this paper, we study a wide range of properties which includes most of the ones used by existing CSP algorithms as well as some which have not yet been considered in the literature, and we investigate their use in CSP solving. We clarify the relationships between these notions and characterise the complexity of the problem of checking them. Following the CSP approach, we then determine a number of relaxations (for instance local versions) which provide sufficient conditions whose detection is tractable. This work is a first step towards a comprehensive framework for CSP properties, and it also shows that new notions still remain to be exploited.