List of complexity classes

From Wikipedia, the free encyclopedia

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
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
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)
RLP	Solvable in logarithmic space and 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.
UP	Unambiguous Non-Deterministic Polytime functions.
ZPP	Solvable by randomized algorithms (answer is always right, average running time is polynomial)

[edit] External links

• Complexity Zoo - list of over 400 complexity classes and their properties