computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

, a

computational problem In theoretical computer science, a computational problem is one that asks for a solution in terms of an algorithm. For example, the problem of factoring :"Given a positive integer ''n'', find a nontrivial prime factor of ''n''." is a computati ...

is complete for a

complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...

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 In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

, 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 In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

. 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 In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP if and o ...

, 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 An oracle is a person or thing considered to provide insight, wise counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. If done through occultic means, it is a form of divination. Descript ...

M) has no complete problems.

References

{{reflist Computational complexity theory