View Related Documents

Abstract

Many combinatorial search problems can be expressed as lsquoconstraint satisfaction problemsrsquo, and this class of problems is known to be NP-complete in general. In this paper we investigate lsquodisjunctive constraintsrsquo, that is, constraints which have the form of the disjunction of two constraints of specified types. We show that when the constraint types involved in the disjunction have a certain property, which we call lsquoindependencersquo, and when a certain restricted class of problems is tractable, then the class of all problems involving these 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 classes which have not previously been identified.

Keywords  Constraint satisfaction problem - complexity - NP-completeness

Fulltext Preview

Image of the first page of the fulltext document