In computational complexity theory, SNP is a complexity classcontaining 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 expressible by a second-order logicformula of the following form: where are relations of the structure, are unknown relations, and is a quantifier-free formula: any boolean combination of the relations. That is, only existential second-order quantification is allowed and only universal first-order quantification is allowed. If existential quantification over vertices were also allowed, the resulting complexity class would be equal to NP, a fact known as Fagin's theorem. For example, SNP contains 3-Coloring, because it can be expressed by the following formula: Here denotes the adjacency relation of the input graph, while the sets correspond to sets of vertices colored with one of the 3 colors. Similarly, SNP contains the k-SAT problem: the boolean satisfiability problem where the formula is restricted to conjunctive normal form and to at most k literals per clause, where k is fixed.
MaxSNP
An analogous definition considers optimization problems, when instead of asking a formula to be satisfied for all tuples, one wants to maximize the number of tuples for which it is satisfied. That is, MaxSNP0 is defined as the class of optimization problems on relational structures expressible in the following form: MaxSNP is then defined as the class of all problems with an L-reduction to problems in MaxSNP0. For example, MAX-3SAT is a problem in MaxSNP0: given an instance of 3-CNF-SAT, find an assignment satisfying as many clauses as possible. In fact, it is a natural complete problem for MaxSNP. There is a fixed-ratio approximation algorithm to solve any problem in MaxSNP, hence MaxSNP is contained in APX, the class of all problems approximable to within some constant ratio. In fact the closure of MaxSNP under PTAS reductions is equal to APX; that is, every problem in APX has a PTAS reduction to it from some problem in MaxSNP. In particular, every MaxSNP-complete problem is also APX-complete, and hence does not admit a PTAS unlessP=NP. However, the proof of this relies on the PCP theorem, while proofs of MaxSNP-completeness are often elementary.
