Monotone monadic SNP and constraint satisfaction
Tomás Feder, Moshe Y. Vardi · 1993
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 constraintsatisfaction 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.