Open AccessTractable Set Constraints
Author(s) -
Manuel Bodirsky,
Martin Hils
Publication year - 2012
Publication title -
journal of artificial intelligence research/the journal of artificial intelligence research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.79
H-Index - 123
eISSN - 1943-5037
pISSN - 1076-9757
DOI - 10.1613/jair.3747
Subject(s) - constraint satisfaction problem , sublanguage , class (philosophy) , set (abstract data type) , constraint satisfaction , computer science , answer set programming , constraint (computer aided design) , theoretical computer science , representation (politics) , set cover problem , mathematics , artificial intelligence , programming language , geometry , probabilistic logic , politics , political science , law
Many fundamental problems in artificial intelligence, knowledge representation, and verification involve reasoning about sets and relations between sets and can be modeled as set constraint satisfaction problems (set CSPs). Such problems are frequently intractable, but there are several important set CSPs that are known to be polynomial-time tractable. We introduce a large class of set CSPs that can be solved in quadratic time. Our class, which we call EI, contains all previously known tractable set CSPs, but also some new ones that are of crucial importance for example in description logics. The class of EI set constraints has an elegant universal-algebraic characterization, which we use to show that every set constraint language that properly contains all EI set constraints already has a finite sublanguage with an NP-hard constraint satisfaction problem.