Complete (complexity)
Encyclopedia
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. If a problem has the property that (if you know how to solve it) it allows you to quickly solve any problem in a complexity class, it is called hard for that class.
More formally, a problem p is called hard for a complexity class C under a given type of reduction
, if there is a reduction of this type from any problem in C to p. If a problem is both hard for a class, and a member of the class, it is complete for that class (under the given type of reduction).
A problem that is complete for a class C is said to be C-complete, and the class of all problems complete for C is denoted C-complete. The first complete class to be defined and the most well-known is NP-complete
, a class that contains many difficult-to-solve problems that arise in practice. Similarly, a problem hard for a class C is called C-hard, e.g. NP-hard
.
Normally it is assumed that the reduction in question does not have higher computational complexity than the class itself. Therefore it may be said that if a C-complete problem has a "computationally easy" solution, then all problems in "C" have an "easy" solution.
Generally, complexity classes that have a recursive enumeration have known complete problems, whereas those that do not, don't have any known complete problems. For example, NP
, co-NP, PLS
, PPA
all have known natural complete problems, while RP
, ZPP, BPP and TFNP
do not have any known complete problems (although such a problem may be discovered in the future).
There are classes without complete problems. For example, Sipser showed that there is a language M such that BPPM (BPP with oracle
M) has no complete problems.
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...
, a computational problem
Computational problem
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring...
is complete for 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:...
if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class. If a problem has the property that (if you know how to solve it) it allows you to quickly solve any problem in a complexity class, it is called hard for that class.
More formally, a problem p is called hard for a complexity class C under a given type of reduction
Reduction (complexity)
In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. Depending on the transformation used this can be used to define complexity classes on a set of problems....
, if there is a reduction of this type from any problem in C to p. If a problem is both hard for a class, and a member of the class, it is complete for that class (under the given type of reduction).
A problem that is complete for a class C is said to be C-complete, and the class of all problems complete for C is denoted C-complete. The first complete class to be defined and the most well-known is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, a class that contains many difficult-to-solve problems that arise in practice. Similarly, a problem hard for a class C is called C-hard, e.g. NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
.
Normally it is assumed that the reduction in question does not have higher computational complexity than the class itself. Therefore it may be said that if a C-complete problem has a "computationally easy" solution, then all problems in "C" have an "easy" solution.
Generally, complexity classes that have a recursive enumeration have known complete problems, whereas those that do not, don't have any known complete problems. For example, NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
, co-NP, PLS
PLS (complexity)
In computational complexity theory, PLS, which stands for Polynomial Local Search, is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem....
, PPA
PPA (complexity)
PPA is a complexity class, standing for "Polynomial Parity Argument" . Introduced by Christos Papadimitriou in 1994 , PPA is a subclass of TFNP...
all have known natural complete problems, while RP
RP (complexity)
In complexity theory, RP is the complexity class of problems for which a probabilistic Turing machine exists with these properties:* It always runs in polynomial time in the input size...
, ZPP, BPP and TFNP
TFNP
In computational complexity theory, the complexity class TFNP is a subclass of FNP where a solution is guaranteed to exist. It stands for "Total Function Nondeterministic Polynomial."...
do not have any known complete problems (although such a problem may be discovered in the future).
There are classes without complete problems. For example, Sipser showed that there is a language M such that BPPM (BPP with oracle
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
M) has no complete problems.