Tractable d isjunctive constraints

摘要

Many combinatorial search problems can be expressed as `constraint satisfaction problems', and this calss of problems is known to be NP-complete in general. In this paper we investigate `disjunctive constraints', that is, constraints which have the form of the disjunction of two constraints of s pecified types. We show that w hen the constraint types involvd in the disjunction have a certain property, which we call `independence;, and when a certain restricted class of problems is tractable, then the class of all problems involving threse disjunctive constraints is tractable. We give examples to show that many known examples of tractable constraint classes arise in this way, and derive new tractable calasses which have not proeviously been identified.