SNP (complexity)
Encyclopedia
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 problem
s.
One characterization of the complexity class
NP
, 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 graph
s 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.
: 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 problem
s is called MaxSNP0 and was defined by Christos Papadimitriou
and Mihalis Yannakakis
in their 1988 paper "Optimization, approximation, and complexity classes."
Papadimitriou and Yannakakis go on to complete this class by defining MaxSNP, the class of all problems with an L-reduction
(linear reduction, not log-space reduction) to problems in MaxSNP0, and show that it has a natural complete
problem: given an instance of 3CNFSAT (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. In fact, for every problem in APX
, the class of all problems approximable to within some constant ratio, there is a PTAS reduction
to it from some problem in MaxSNP; that is, the closure of MaxSNP under PTAS reduction
s is APX.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, SNP (from Strict NP) is a complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
containing a limited subset of NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
based on its logical characterization in terms of graph-theoretical
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
properties. It forms the basis for the definition of the class MaxSNP of optimization problem
Optimization problem
In mathematics and computer science, 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 are continuous or discrete. An optimization problem with discrete...
s.
One characterization of the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
, shown by Ronald Fagin
Ronald Fagin
Ronald Fagin is the Manager of the Foundations of Computer Science group at the IBM Almaden Research Center. He is best known for his pioneering work in database theory, finite model theory, and reasoning about knowledge...
in 1974 and related to Fagin's theorem
Fagin's theorem
Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP...
, is that it is the set of problems that can be reduced to properties of graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
s expressible in existential second-order logic
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....
. 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
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
(SAT) where the formula is restricted to conjunctive normal form
Conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form if it is a conjunction of clauses, where a clause is a disjunction of literals.As a normal form, it is useful in automated theorem proving...
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 problemOptimization problem
In mathematics and computer science, 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 are continuous or discrete. An optimization problem with discrete...
: 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 problem
Function problem
In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...
s is called MaxSNP0 and was defined by Christos Papadimitriou
Christos Papadimitriou
Christos Harilaos Papadimitriou is a Professor in the Computer Science Division at the University of California, Berkeley, United States...
and Mihalis Yannakakis
Mihalis Yannakakis
Mihalis Yannakakis is a Professor of Computer Science at Columbia University. He is noted for his work in computational complexity, databases, and other related fields. He won the Donald E. Knuth Prize in 2005.-Education and career:...
in their 1988 paper "Optimization, approximation, and complexity classes."
Papadimitriou and Yannakakis go on to complete this class by defining MaxSNP, the class of all problems with an L-reduction
L-reduction
In computer science, in particular in the study of approximation algorithms, anL-reduction is a transformation of optimization problems which linearly preserves approximability features...
(linear reduction, not log-space reduction) to problems in MaxSNP0, and show that it has a natural complete
Complete (complexity)
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class...
problem: given an instance of 3CNFSAT (the boolean satisfiability problem
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
with the formula in conjunctive normal form
Conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form if it is a conjunction of clauses, where a clause is a disjunction of literals.As a normal form, it is useful in automated theorem proving...
and at most 3 literals per clause), find an assignment satisfying as many clauses as possible.
There is a fixed-ratio approximation algorithm
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
to solve any problem in MaxSNP. In fact, for every problem in APX
APX
In complexity theory the class APX is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant...
, the class of all problems approximable to within some constant ratio, there is a PTAS reduction
PTAS reduction
In computational complexity theory, a PTAS reduction is a reduction that is often used to perform reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time approximation scheme and is used to define completeness for certain classes of...
to it from some problem in MaxSNP; that is, the closure of MaxSNP under PTAS reduction
PTAS reduction
In computational complexity theory, a PTAS reduction is a reduction that is often used to perform reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time approximation scheme and is used to define completeness for certain classes of...
s is APX.