This is a list of complexity classes in computational complexity theory. 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 doesn't 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 and 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.
If you don't see a class listed (such as Co-UP) you should look under its partner (such as UP).
#P | Count solutions to an NP problem |
#P-complete | The hardest problems in #P |
2-EXPTIME | Solvable with doubly exponential time |
AC0 | A circuit complexity class of bounded depth. |
ACC0 | A circuit complexity class of bounded depth and counting gates. |
AC | A circuit complexity class. |
AH | The arithmetic hierarchy |
AP | The class of problems alternating Turing machines can solve in polynomial time. |
APX | Optimization problems that have approximation algorithms with constant approximation ratio |
AM | Solvable in polynomial time by an Arthur-Merlin protocol |
BPP | Solvable in polynomial time by randomized algorithms (answer is probably right) |
BQP | Solvable in polynomial time on a quantum computer (answer is probably right) |
co-NP | "NO" answers checkable in polynomial time by a non-deterministic machine |
co-NP-complete | The hardest problems in co-NP |
DSPACE(f(n)) | Solvable by a deterministic machine in space O(f(n)). |
DTIME(f(n)) | Solvable by a deterministic machine in time O(f(n)). |
E | Solvable in exponential time with linear exponent |
ELEMENTARY | The union of the classes in the exponential hierarchy |
ESPACE | Solvable in exponential space with linear exponent |
EXP | Same as EXPTIME |
EXPSPACE | Solvable in exponential space |
EXPTIME | Solvable with exponential time |
FNP | The analogue of NP for function problems |
FP | The analogue of P for function problems |
FPNP | The analogue of PNP for function problems; the home of the traveling salesman problem |
FPT | Fixed-parameter tractable |
GapL | Logspace-reducible to computing the integer determinant of a matrix |
IP | Solvable in polynomial time by an interactive proof system |
L | Solvable in logarithmic (small) space |
LOGCFL | Logspace-reducible to a context-free language |
MA | Solvable in polynomial time by a Merlin-Arthur protocol |
NC | Solvable efficiently (in polylogarithmic time) on parallel computers |
NE | Solvable by a non-deterministic machine in exponential time with linear exponent |
NESPACE | Solvable by a non-deterministic machine in exponential space with linear exponent |
NEXP | Same as NEXPTIME |
NEXPSPACE | Solvable by a non-deterministic machine in exponential space |
NEXPTIME | Solvable by a non-deterministic machine in exponential time |
NL | "YES" answers checkable in logarithmic space |
NONELEMENTARY | Complement of ELEMENTARY. |
NP | "YES" answers checkable in polynomial time (see complexity classes P and NP) |
NP-complete | The hardest or most expressive problems in NP |
NP-easy | Analogue to PNP for function problems; another name for FPNP |
NP-equivalent | The hardest problems in FPNP |
NP-hard | Either NP-complete or harder |
NSPACE(f(n)) | Solvable by a non-deterministic machine in space O(f(n)). |
NTIME(f(n)) | Solvable by a non-deterministic machine in time O(f(n)). |
P | Solvable in polynomial time |
P-complete | The hardest problems in P to solve on parallel computers |
P/poly | Solvable in polynomial time given an "advice string" depending only on the input size |
PCP | Probabilistically Checkable Proof |
PH | The union of the classes in the polynomial hierarchy |
PNP | Solvable in polynomial time with an oracle for a problem in NP; also known as Δ2P |
PP | Probabilistically Polynomial (answer is right with probability slightly more than ½) |
PR | Solvable by recursively building up arithmetic functions. |
PSPACE | Solvable with polynomial memory. |
PSPACE-complete | The hardest problems in PSPACE. |
R | Solvable in a finite amount of time. |
RE | Problems to which we can answer "YES" in a finite amount of time, but a "NO" answer might never come. |
RL | Solvable in logarithmic space by randomized algorithms (NO answer is probably right, YES is certainly right) |
RP | Solvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right) |
SL | Problems log-space reducible to determining if a path exist between given vertices in an undirected graph. In October 2004 it was discovered that this class is in fact equal to L. |
S2P | one round games with simultaneous moves refereed deterministically in polynomial time |
TFNP | Total function problems solvable in non-deterministic polynomial time. A problem in this class has the property that every input has an output whose validity may be checked efficiently, and the computational challenge is to find a valid output. |
UP | Unambiguous Non-Deterministic Polytime functions. |
ZPL | Solvable by randomized algorithms (answer is always right, average running space is logarithmic) |
ZPP | Solvable by randomized algorithms (answer is always right, average running time is polynomial) |
Famous quotes containing the words list of, list, complexity and/or classes:
“Religious literature has eminent examples, and if we run over our private list of poets, critics, philanthropists and philosophers, we shall find them infected with this dropsy and elephantiasis, which we ought to have tapped.”
—Ralph Waldo Emerson (18031882)
“The advice of their elders to young men is very apt to be as unreal as a list of the hundred best books.”
—Oliver Wendell Holmes, Jr. (18411935)
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put intelephonic, technological and relationalto alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)
“One marvels why ... the middle classes still insist on so much discomfort for their children at such expense to themselves.”
—E.M. (Edward Morgan)