SNP (complexity)
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.
One characterization of the NP complexity class, as shown by Ronald Fagin in 1974 and related to Fagin's theorem, is that it is the set of problems that can be reduced to properties of graphs expressible in existential second-order logic. This logic allows universal (∀) and existential (∃) quantification over vertices, but only existential quantification over sets of vertices and relations between vertices. SNP retains existential quantification over sets and relations, but only permits universal quantification over vertices.
SNP contains k-SAT, 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.
MaxSNP
Suppose there is a problem in SNP characterized by a formula of the form "∃A p(A)" where A is some set or relation and p is a first-order predicate that can use it. One can define a corresponding optimization problem: to find the relation or set that maximizes the number of tuples or elements, respectively, that satisfy the predicate p. The class of all such function problems is called MaxSNP0 and was defined by Christos Papadimitriou and Mihalis Yannakakis in their 1991 paper "Optimization, approximation, and complexity classes."[1]
MaxSNP is defined as the class of all problems with an L-reduction (linear reduction, not log-space reduction) to problems in MaxSNP0. It has a natural complete problem: given an instance of 3-CNF-SAT (the boolean satisfiability problem with the formula in conjunctive normal form and at most 3 literals per clause), find an assignment satisfying as many clauses as possible.
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 (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. In particular, every MaxSNP-complete problem (under L-reductions or under AP-reductions) is also APX-complete (under PTAS reductions), and hence does not admit a PTAS unless P=NP. However, the proof of this relies on the PCP theorem, while proofs of MaxSNP-completeness are often elementary.
References
- ^ Papadimitriou, Christos H.; Yannakakis, Mihalis (1991). "Optimization, approximation, and complexity classes". J. Comput. Syst. Sci. 43 (3): 425–440. Zbl 0765.68036.
- Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Finite model theory and its applications. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. p. 350. ISBN 978-3-540-00428-8. Zbl 1133.03001.