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.
Type de document :
Communication dans un congrès
McGuinness D.L.; Ferguson G. AAAI Conference on Artificial Intelligence, Jul 2004, San Jose, CA, United States. MIT Press, THE NINETEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, pp.112-117, 2004, 〈http://www.aaai.org/Conferences/AAAI/aaai04.php〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00108868
Contributeur : Christine Carvalho de Matos <>
Soumis le : mardi 14 février 2017 - 17:28:36
Dernière modification le : jeudi 11 janvier 2018 - 06:26:23
Document(s) archivé(s) le : lundi 15 mai 2017 - 17:46:34

Fichier

aaai04.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : lirmm-00108868, version 1

Collections

Citation

Christian Bessière, Emmanuel Hébrard, Brahim Hnich, Toby Walsh. The Complexity of Global Constraints. McGuinness D.L.; Ferguson G. AAAI Conference on Artificial Intelligence, Jul 2004, San Jose, CA, United States. MIT Press, THE NINETEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, pp.112-117, 2004, 〈http://www.aaai.org/Conferences/AAAI/aaai04.php〉. 〈lirmm-00108868〉

Partager

Métriques

Consultations de la notice

105

Téléchargements de fichiers

98