This is a list of
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
es in
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
. For other computational and complexity subjects, see
list of computability and complexity topics
This is a list of computability and complexity topics, by Wikipedia page.
Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard computa ...
.
Many of these classes have a 'co' partner which consists of the
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-class ...
s of all languages in the original class. For example, if a language L is in NP then the complement of L is in co-NP. (This does not mean that the complement of NP is co-NP—there are languages which are known to be in both, and other languages which are known to be in neither.)
"The hardest problems" of a class refer to problems which belong to the class such that every other problem of that class can be reduced to it. Furthermore, the reduction is also a problem of the given class, or its subset.
References
External links
Complexity Zoo- list of over 500 complexity classes and their properties
{{DEFAULTSORT:Complexity Classes
*
Mathematics-related lists