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. If a problem has the property that 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).^{[citation needed]}

There are classes without complete problems. For example, Sipser showed that there is a language M such that BPP^M (BPP with oracle M) has no complete problems.^[1]

References

1. ^ M. Sipser. On relativization and the existence of complete sets, Proceedings of ICALP'82, Springer-Verlag Lecture Notes in Computer Science volume 140, pp. 523-531, 1982.