Skip to Main content Skip to Navigation
Conference papers

The Complexity of Global Constraints

Christian Bessière 1 Emmanuel Hébrard 2 Brahim Hnich 2 Toby Walsh 2
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We study the computational complexity of reasoning with global constraints. We show that reasoning with such constraints is intractable in general. We then demonstrate how the same tools of computational com- plexity can be used in the design and analysis of spe- cific global constraints. In particular, we illustrate how computational complexity can be used to determine when a lesser level of local consistency should be en- forced, when decomposing constraints will lose prun- ing,andwhencombiningconstraintsistractable.We also show how the same tools can be used to study symmetry breaking, meta-constraints like the cardinal- ity constraint, and learning nogoods.
Document type :
Conference papers
Complete list of metadata
Contributor : Christine Carvalho de Matos Connect in order to contact the contributor
Submitted on : Tuesday, February 14, 2017 - 5:28:36 PM
Last modification on : Friday, October 22, 2021 - 3:07:33 PM
Long-term archiving on: : Monday, May 15, 2017 - 5:46:34 PM


Publisher files allowed on an open archive


  • HAL Id : lirmm-00108868, version 1



Christian Bessière, Emmanuel Hébrard, Brahim Hnich, Toby Walsh. The Complexity of Global Constraints. AAAI Conference on Artificial Intelligence, Jul 2004, San Jose, CA, United States. pp.112-117. ⟨lirmm-00108868⟩



Record views


Files downloads