Class Description

MaxSNP: Maximization SNP

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].

Linked From

APX: Approximable

The subclass of NPO problems that admit constant-factor approximation algorithms. (I.e., there is a polynomial-time algorithm that is guaranteed to find a solution within a constant factor of the optimum cost.)

Contains PTAS.

Equals the closure of MaxSNP and of MaxNP under PTAS reduction [KMS+99], [CT94].

Defined in [ACG+99].

More about...


GLO: Guaranteed Local Optima

The class of NPO problems which have the property that for all locally optimal solutions, the ratio between the values of the local and global optima is upper-bounded by a constant.

Defined in [AP95], where it was also shown that GLO is strictly contained in APX.

[KMS+99] showed that MaxSNP is not contained in GLO.

More about...


MaxNP: Maximization NP

Has the same relation to NP as MaxSNP does to SNP.

Contains MaxPB.

The closure of MaxNP under PTAS reduction is APX [KMS+99], [CT94].

More about...


SNP: Strict NP

[Fag74] showed that NP is precisely the class of decision problems reducible to a graph-theoretic property expressible in second-order existential logic.

Then SNP is the class of decision problems reducible to a graph-theoretic predicate with only universal quantifiers over vertices, no existential quantifiers. As an example, k-SAT (CNF satisfiability with at most k literals per clause, for k a constant) is in SNP. But general SAT is not in SNP, basically because we're not allowed to say, "There exists a literal in this clause that satisfies the clause."

Contains MMSNP.

See also: MaxSNP.

More about...