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 metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00108868
Contributor : Christine Carvalho de Matos <>
Submitted on : Tuesday, February 14, 2017 - 5:28:36 PM
Last modification on : Thursday, May 24, 2018 - 3:59:23 PM
Long-term archiving on : Monday, May 15, 2017 - 5:46:34 PM

File

aaai04.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : lirmm-00108868, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

293

Files downloads

265