  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.
