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.