The class of function problems expressible as "find a relation such that the set of k-tuples for which a given SNP predicate holds has maximum cardinality."
For example (see [Pap94]), the Max-Cut problem can be expressed as follows:
Defined in [PY88].
The class of optimization problems reducible by an "L-reduction" to a problem in MaxSNP0. (Note: 'L' stands for linear -- this is not the same as an L reduction! For more details see [PY88].)
Defined in [PY88], where the following was also shown:
The closure of MaxSNP under PTAS reduction is APX [KMS+99], [CT94].