On Minimal Constraint Networks
Georg Gottlob
Abstract
In a minimal binary constraint network, every tuple of a constraint relation can be extended to a solution. It was conjectured that computing a solution to such a network is NP hard. We prove this conjecture. We also prove a conjecture by Dechter and Pearl stating that for k ≥ 2 it is NP-hard to decide whether a constraint network can be decomposed into an equivalent k-ary constraint network, and study related questions.
Details
| Address |
Perugia‚ Italy |
| Book Title |
Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming‚ CP 2011 |
| Year |
2011 |
Links
Related pages
|
People |
|
|
Projects |
Constraint Satisfaction for Configuration: Logical Fundamentals, Algorithms, and Complexity |