Reasoning about NP-complete Constraints

Reasoning about NP-complete Constraints

Emmanuel Hebrard

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Early Career. Pages 5672-5676. https://doi.org/10.24963/ijcai.2018/807

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.
Keywords:
Constraints and SAT: Constraint Satisfaction
Constraints and SAT: Global Constraints
Knowledge Representation and Reasoning: Computational Complexity of Reasoning