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 o ...
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 ...
. For other computational and complexity subjects, see
list of computability and complexity topics.
Many of these classes have a 'co' partner which consists of the
complements 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