2011/03/08 by Georg Gottlob, Gottlob, Georg
Computer Science · #Advanced Graph Theory Research #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #cs.AI #cs.CC #cs.DB
paper · pdf · doi:10.48550/arxiv.1103.1604
Preprint - to appear in Artificial Intelligence. (Full version of the CP'2011 paper with same title)
openalex publication_date 2011/03/08 · arxiv created 2012/07/25 · arxiv updated 2012/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a minimal binary constraint network, every tuple of a constraint relation can be extended to a solution. The tractability or intractability of computing a solution to such a minimal network was a long standing open question. Dechter conjectured this computation problem to be 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 single constraint can be decomposed into an equivalent k-ary constraint network. We show that this holds even in case of bi-valued constraints where k≥3, which proves another conjecture of Dechter and Pearl. Finally, we establish the tractability frontier for this problem with respect to the domain cardinality and the parameter k.