TRACTABLE CONSTRAINTS ON ORDERED DOMAINS

Finding solutions to a constraint satisfaction problem is known to be an NP-complete problem in general, but may be tractable in cases where either the set of allowed constraints or the graph structure is restr icted. In this paper we identify a restricted set of contraints which gives rise to a class of tractable problems. This class generalizes th e notion of a Horn formula in propositional logic to larger domain siz es. We give a polynomial time algorithm for solving such problems, and prove that the class of problems generated by any larger set of const raints is NP-complete.