|
NeuroCOLT
Technical Report NC-TR-95-019
An Algebraic
Characterization of Tractable Constraints
Peter
Jeavons
Royal Holloway, University of London
Abstract
Many combinatorial search problems may be expressed as `constraint
satisfaction problems', and this class of problems is known to be
NP-complete. In this paper we investigate what restrictions must be
imposed on the allowed constraints in order to ensure tractability.
We describe a simple algebraic closure condition, and show that this
is both necessary and sufficient to ensure tractability in Boolean
valued problems. We also demonstrate that this condition is necessary
for problems with arbitrary finite domains.
Download Compressed
Postscript
|