2013/07/10 by David A. Cohen, Cohen, David A., Peter Jeavons +5
Computer Science · #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #Data Management and Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.1307.2867
openalex publication_date 2013/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the complexity of constraint satisfaction problems involving global constraints, i.e., special-purpose constraints provided by a solver and represented implicitly by a parametrised algorithm. Such constraints are widely used; indeed, they are one of the key reasons for the success of constraint programming in solving real-world problems. Previous work has focused on the development of efficient propagators for individual constraints. In this paper, we identify a new tractable class of constraint problems involving global constraints of unbounded arity. To do so, we combine structural restrictions with the observation that some important types of global constraint do not distinguish between large classes of equivalent solutions.