Class Description

CSP: Constraint Satisfaction Problems

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 ${\displaystyle \{0,1\}}$) containing ${\displaystyle C_{0},C_{1},C_{2},C_{3}}$:

${\displaystyle {\begin{matrix}C_{0}&=&\{0,1\}^{3}\backslash (0,0,0)\\C_{1}&=&\{0,1\}^{3}\backslash (1,0,0)\\C_{2}&=&\{0,1\}^{3}\backslash (1,1,0)\\C_{3}&=&\{0,1\}^{3}\backslash (1,1,1)\end{matrix}}}$

For example, a 3SAT clause ${\displaystyle (x\vee y\vee \neg z)}$ is represented in the CSP construction as ${\displaystyle C_{1}(z,x,y)\in I}$. By similar constructions, any k-SAT problem can be seen to be in CSP. The class also includes Graph k-Coloring (for ${\displaystyle k\in \mathbb {N} }$), Graph H-Coloring (for some graph ${\displaystyle H}$) and Linear Programming mod ${\displaystyle q}$.

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.

Linked From

MMSNP: Monadic Monotone SNP

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:

1. The second order existentially quantified variables, known as the proof relations, are restricted to be monadic. (Monadic relations can be treated as sets.)
2. Any relations in the formula other than the proof relations must occur only negated (the formula is monotone).
3. No inequality relations can occur in the formula.

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.

More about...