{{Short description|Complexity class}} 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: : <math>\exists S_1 \dots \exists S_\ell \, \forall v_1 \dots \forall v_m \,\phi(R_1,\dots,R_k,S_1,\dots,S_\ell,v_1,\dots,v_m)</math> where <math>R_1,\dots,R_k</math> are relations of the structure (such as the adjacency relation, for a graph), <math>S_1,\dots,S_\ell</math> are unknown relations (sets of tuples of vertices), and <math>\phi</math> is a quantifier-free formula: any boolean combination of the relations.<ref>{{cite book| last1=Feder | first1= Tomás |last2=Vardi |first2=Moshe Y. | title= Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | chapter= Monotone monadic SNP and constraint satisfaction | year=1993 | pages= 612–622 | doi=10.1145/167088.167245| isbn= 0897915917 | s2cid= 9229294 | doi-access=free }}</ref> That is, only existential second-order quantification (over relations) is allowed and only universal first-order quantification (over vertices) is allowed. 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: : <math>\exists S_1 \exists S_2 \exists S_3 \, \forall u \forall v \, \bigl( S_1(u) \vee S_2(u) \vee S_3(u) \bigr) \, \wedge \, \bigl( E(u,v)\,\implies\,(\neg S_1(u) \vee \neg S_1(v))\,\wedge\,\left(\neg S_2(u) \vee \neg S_2(v)\right)\,\wedge\,(\neg S_3(u) \vee \neg S_3(v)) \bigr) </math> Here <math>E</math> denotes the adjacency relation of the input graph, while the sets (unary relations) <math>S_1,S_2,S_3</math> correspond to sets of vertices colored with one of the 3 colors. 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.
== 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, '''MaxSNP<sub>0</sub>''' is defined as the class of optimization problems on relational structures expressible in the following form: : <math>\max\limits_{S_1,\dots,S_\ell} |\{ (v_1, \dots, v_m) \colon \phi(R_1,\dots,R_k,S_1,\dots,S_\ell,v_1,\dots,v_m)\}|</math> '''MaxSNP''' is then defined as the class of all problems with an L-reduction (''linear reduction'', not ''log-space reduction'') to problems in '''MaxSNP<sub>0</sub>'''.<ref>{{cite journal | last1=Papadimitriou | first1=Christos H. | last2=Yannakakis | first2=Mihalis | title=Optimization, approximation, and complexity classes | zbl=0765.68036 | journal=J. Comput. Syst. Sci. | volume=43 | number=3 | pages=425–440 | year=1991 | doi=10.1016/0022-0000(91)90023-X | doi-access= }}</ref> For example, MAX-3SAT is a problem in '''MaxSNP<sub>0</sub>''': 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. 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 (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.
== See also == * APX
== References == {{reflist}} * {{cite book | last1=Grädel | first1=Erich | last2=Kolaitis | first2=Phokion G. | last3=Libkin | first3=Leonid | author3-link=Leonid Libkin | last4=Maarten | first4=Marx | last5=Spencer | first5=Joel | author5-link=Joel Spencer | last6=Vardi | first6=Moshe Y. | author6-link=Moshe Y. Vardi | last7=Venema | first7=Yde | last8=Weinstein | first8=Scott | title=Finite model theory and its applications | url=https://archive.org/details/finitemodeltheor00grde | url-access=limited | zbl=1133.03001 | series=Texts in Theoretical Computer Science. An EATCS Series | location=Berlin | publisher=Springer-Verlag | isbn=978-3-540-00428-8 | year=2007 | page=[https://archive.org/details/finitemodeltheor00grde/page/n358 350] }}
==External links== *{{CZoo|SNP|S#snp}} *{{CZoo|MaxSNP|M#maxsnp}} *{{CZoo|MaxSNP<sub>0</sub>|M#maxsnp0}}
Category:Complexity classes