Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Complete (complexity)
Summary
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 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 BPPM (BPP with oracle M) has no complete problems.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.