Skip to Main content Skip to Navigation
Conference papers

Reasoning About NP-complete Constraints

Emmanuel Hébrard 1 
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : The concept of local consistency-making global deductions from local infeasibility-is central to constraint programming. When reasoning about NP-complete constraints, however, since achieving a "complete" form of local consistency is often considered too hard, we need other tools to design and analyze propagation algorithms. In this paper, we argue that NP-complete constraints are an essential part of constraint programming , that designing dedicated methods has lead to, and will bring, significant breakthroughs, and that we need to carefully investigate methods to deal about a necessarily incomplete inference. In particular, we advocate the use of fixed-parameter tractability and kernelization to this purpose.
Document type :
Conference papers
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download

https://hal.laas.fr/hal-01873503
Contributor : Emmanuel Hebrard Connect in order to contact the contributor
Submitted on : Thursday, September 13, 2018 - 12:45:28 PM
Last modification on : Monday, July 4, 2022 - 10:09:49 AM
Long-term archiving on: : Friday, December 14, 2018 - 1:25:30 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01873503, version 1

Citation

Emmanuel Hébrard. Reasoning About NP-complete Constraints. 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), Jul 2018, Stockholm, Sweden. 5p. ⟨hal-01873503⟩

Share

Metrics

Record views

13

Files downloads

0