List of Complexity Classes

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:

    Modern tourist guides have helped raised tourist expectations. And they have provided the natives—from Kaiser Wilhelm down to the villagers of Chichacestenango—with a detailed and itemized list of what is expected of them and when. These are the up-to- date scripts for actors on the tourists’ stage.
    Daniel J. Boorstin (b. 1914)

    We saw the machinery where murderers are now executed. Seven have been executed. The plan is better than the old one. It is quietly done. Only a few, at the most about thirty or forty, can witness [an execution]. It excites nobody outside of the list permitted to attend. I think the time for capital punishment has passed. I would abolish it. But while it lasts this is the best mode.
    Rutherford Birchard Hayes (1822–1893)

    In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...
    Marcel Proust (1871–1922)

    The most powerful lessons about ethics and morality do not come from school discussions or classes in character building. They come from family life where people treat one another with respect, consideration, and love.
    Neil Kurshan (20th century)