The Complexity of Global Constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2004

The Complexity of Global Constraints

Résumé

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.
Fichier principal
Vignette du fichier
aaai04.pdf (86.67 Ko) Télécharger le fichier
Origine Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

lirmm-00108868 , version 1 (14-02-2017)

Identifiants

  • HAL Id : lirmm-00108868 , version 1

Citer

Christian Bessiere, 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⟩
219 Consultations
176 Téléchargements

Partager

More