On Minimal Constraint Networks
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 dec...
| Autore principale: | |
|---|---|
| Natura: | Conference item |
| Pubblicazione: |
Perugia‚ Italy
2011
|
| Riassunto: | 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. |
|---|