About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 1993
Conference paper
Monotone monadic SNP and constraint satisfaction
Abstract
A constraint-satisfaction problem is given by a pair I (the instance) and T (the template) of finite relational structures over the same vocabulary. The problem is satisfied if there is a homomorphism from 1 to T. It is well-known that the constraint-satisfaction problem is NP-complete. In practice, however, one often encounters the situation where the template T is fixed and it is only the instance I that varies. We define CSP to be the class of constraint-satisfaction problems with respect to fixed templates. It is easy to see that CSP is contained in NP and that CSP contains both problems in P and NP-complete problems. We pose the question whether every problem in CSP is either in P or is NP-complete, and attempt to classify which problems in CSP are in P and which are NP-complete.