Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Complete (complexity)
open-in-new
<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, a <a href="/facts/Computational_problem/jQ7bYUVh">computational problem</a> is complete for a <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a> if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class. </p><p>More formally, a problem <i>p</i> is called hard for a complexity class <i>C</i> under a given type of <a href="/facts/Reduction_(complexity)/IVWF7a1c">reduction</a> if there exists a reduction (of the given type) from any problem in <i>C</i> to <i>p</i>. 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). </p><p>A problem that is complete for a class <i>C</i> is said to be C-complete, and the class of all problems complete for <i>C</i> is denoted C-complete. The first complete class to be defined and the most well known is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>, a class that contains many difficult-to-solve problems that arise in practice. Similarly, a problem hard for a class <i>C</i> is called C-hard, e.g. <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>. </p><p>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 <i>C-complete</i> problem has a "computationally easy" solution, then all problems in "C" have an "easy" solution. </p><p>Generally, complexity classes that have a recursive enumeration have known complete problems, whereas classes that lack a recursive enumeration have none. For example, <a href="/facts/NP_(complexity)/6muUfVMI">NP</a>, <a href="/facts/Co-NP/M67JgWNa">co-NP</a>, <a href="/facts/PLS_(complexity)/s4QGR4f2">PLS</a>, <a href="/facts/PPA_(complexity)/jTGW1rcp">PPA</a> all have known natural complete problems. </p><p>There are classes without complete problems. For example, Sipser showed that there is a language M such that BPPM (BPP with <a href="/facts/Oracle_machine/6ScMuvvY">oracle</a> M) has no complete problems. </p>