HOME

TheInfoList



OR:

In
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, SNP (from Strict NP) is a
complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...
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 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 Ma ...
of
optimization problem In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables ...
s. It is defined as the class of problems that are properties of relational structures (such as
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
s) expressible by a
second-order logic In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory. First-order logic quantifies onl ...
formula of the following form: : \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), where R_1,\dots,R_k are relations of the structure (such as the adjacency relation, for a graph), S_1,\dots,S_\ell are unknown relations (sets of tuples of vertices), and \phi is a quantifier-free formula: any boolean combination of the relations. 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 Fagin's theorem is the oldest result of descriptive complexity theory, a branch of computational complexity theory that characterizes complexity classes in terms of logic-based descriptions of their problems rather than by the behavior of algorithm ...
. 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: : \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) . Here E denotes the adjacency relation of the input graph, while the sets (unary relations) S_1,S_2,S_3 correspond to sets of vertices colored with one of the 3 colors. Similarly, SNP contains the ''k''-SAT problem: the
boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
(SAT) where the formula is restricted to
conjunctive normal form In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a can ...
and to at most ''k'' literals per clause, where ''k'' is fixed.


MaxSNP

An analogous definition considers
optimization problem In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables ...
s, 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: : \max\limits_ , \, MaxSNP is then defined as the class of all problems with an
L-reduction In computer science, particularly the study of approximation algorithms, an L-reduction ("''linear reduction''") is a transformation of optimization problems which linearly preserves approximability features; it is one type of approximation-preserv ...
(''linear reduction'', not ''log-space reduction'') to problems in MaxSNP0. For example, MAX-3SAT is a problem in MaxSNP0: given an instance of 3-CNF-SAT (the
boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
with the formula in
conjunctive normal form In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a can ...
and at most 3 literals per clause), find an assignment satisfying as many clauses as possible. In fact, it is a natural
complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...
problem for MaxSNP. There is a fixed-ratio
approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...
to solve any problem in MaxSNP, hence MaxSNP is contained in
APX In computational complexity theory, the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor ap ...
, the class of all problems approximable to within some constant ratio. In fact the closure of MaxSNP under
PTAS reduction In computational complexity theory, a PTAS reduction is an approximation-preserving reduction that is often used to perform reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time approx ...
s (slightly more general than L-reductions) is equal to APX; that is, every problem in APX has a
PTAS reduction In computational complexity theory, a PTAS reduction is an approximation-preserving reduction that is often used to perform reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time approx ...
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 In computational complexity theory, the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor ap ...


References

*


External links

* * *{{CZoo, MaxSNP0, M#maxsnp0 Complexity classes