Editing Complete (complexity)

{{Short description|Notion of the "hardest" or "most general" problem in a complexity class}}
{{Refimprove|date=October 2008}}
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 (complexity)|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 recursive enumeration have known complete problems, whereas classes that lack a recursive enumeration have none. For example, [[NP (complexity)|NP]], [[co-NP]], [[PLS (complexity)|PLS]], [[PPA (complexity)|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'''<sup>'''M'''</sup> ('''BPP''' with [[oracle machine|oracle]] '''M''') has no complete problems.<ref>{{Cite book | doi=10.1007/BFb0012797| chapter=On relativization and the existence of complete sets| title=Automata, Languages and Programming| volume=140| pages=523–531| series=Lecture Notes in Computer Science| year=1982| last1=Sipser| first1=Michael| isbn=978-3-540-11576-2}}</ref>

== References ==
{{reflist}}

[[Category:Computational complexity theory]]