The Complexity of Global Constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2004

The Complexity of Global Constraints

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.
Fichier principal
Vignette du fichier
aaai04.pdf (86.67 Ko) Télécharger le fichier
Origin Publisher files allowed on an open archive

Dates and versions

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

Identifiers

  • HAL Id : lirmm-00108868 , version 1

Cite

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⟩
213 View
170 Download

Share

More