Complete (complexity)

---

title: "Complete (complexity)" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["computational-complexity-theory"] description: "Notion of the "hardest" or "most general" problem in a complexity class" topic_path: "technology/computing" source: "https://en.wikipedia.org/wiki/Complete_(complexity)" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Notion of the "hardest" or "most general" problem in a complexity class ::

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 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 computable enumeration have known complete problems, whereas classes that lack a computable 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 BPPM (BPP with oracle M) has no complete problems.

References

References

1. (1982). "Automata, Languages and Programming".

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::