In computational complexity theory, SNP (from Strict NP) is a complexity class containing a limited subset of NP based on its logical characterization in terms of graph-theoretical properties.
It forms the basis for the definition of the class MaxSNP of optimization problems.
It is defined as the class of problems that are properties of relational structures (such as graphs) expressible by a second-order logic formula of the following form: where
If existential quantification over vertices were also allowed, the resulting complexity class would be equal to NP (more precisely, the class of those properties of relational structures that are in NP), a fact known as Fagin's theorem.
For example, SNP contains 3-Coloring (the problem of determining whether a given graph is 3-colorable), because it can be expressed by the following formula: Here
Similarly, SNP contains the k-SAT problem: the boolean satisfiability problem (SAT) where the formula is restricted to conjunctive normal form and to at most k literals per clause, where k is fixed.
In fact the closure of MaxSNP under PTAS reductions (slightly more general than L-reductions) is equal to APX; that is, every problem in APX has a PTAS reduction to it from some problem in MaxSNP.