Complete (complexity)

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Complete" complexity – news · newspapers · books · scholar · JSTOR (October 2008) (Learn how and when to remove this message)

In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") 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 (of the given type) 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 (for that 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

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.

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