Complete (complexity)


In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" problems in the complexity class.
More formally, a problem p is called hard for a complexity class C under a given type of reduction if there exists a reduction from any problem in C to p. If a problem is both hard for the class and a member of the class, it is complete for that class.
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 classes that lack a recursive enumeration have none. For example, NP, co-NP, PLS, PPA all have known natural complete problems, while RP, ZPP, BPP and TFNP have no known complete problems.
There are classes without complete problems. For example, Sipser showed that there is a language M such that BPPM has no complete problems.