Defined in [FV93] as the class of languages corresponding to fixed templates (where a template is a set of allowed constraints on values and variables) in the general Constraint Satisfaction Problem. Under this construction, 3SAT may be expressed as the fixed template (over the alphabet ) containing :
For example, a 3SAT clause is represented in the CSP construction as . By similar constructions, any k-SAT problem can be seen to be in CSP. The class also includes Graph k-Coloring (for ), Graph H-Coloring (for some graph ) and Linear Programming mod .
In [FV93], where the class is defined, the authors show that every problem in MMSNP is reducible under randomized polynomial-time reductions to a problem in CSP.
Defined in [FV93] as a subclass of SNP. There are three syntactic restrictions defining the subclass MMSNP, based on the form of the SNP formula defining the language:
MMSNP seems to obey dichotomy, by excluding languages that are NP-intermediate. This is still open but widely believed. Dropping any of the restrictions monotone/monadic/without inequalities allows NP-intermediate languages unless P = NP, since any problem in NP is polynomial time equivalent to a problem in each of these broader classes. MMSNP therefore seems to be a maximal fragment of NP where NP-intermediate languages are excluded.
Every constraint satisfaction problem with a fixed target structure is expressible in MMSNP, and there is a polynomial time Turing reduction from every MMSNP query to finitely many constraint satisfaction problems. MMSNP therefore seems to capture the class of constraint satisfaction problems with fixed templates, CSP.