List of complexity classes

This is a list of complexity classes considered in complexity theory.

The classes use different machine models in their definitions . The most important models are Turing machines ; these can work deterministic , nondeterministic or probabilistic . Time complexity and memory space complexity are considered as complexity measures (depending on the problem size or input length n). The estimation of specific runtime or storage space consumption is expressed using the Landau notation .

For each class - if possible - the definition in DTIME , DSPACE , NTIME or NSPACE notation, as well as a short explanation in natural language, is given.

designation	definition	description
#P
# P-complete		The toughest problems in #P.
AT THE		Solvable in polynomial time using an Arthur Merlin protocol (see English ).
BPP		Solvable in polynomial time with a low error probability using a probabilistic Turing machine.
BQP		Solvable in polynomial time with a low probability of error by a quantum computer .
Co-NP		Solutions are falsifiable in polynomial time.
DSPACE (f ( n ))		Solvable by a deterministic Turing machine in O (f ( n )) space.
DTIME (f ( n ))		Solvable by a deterministic Turing machine in O (f ( n )) time.
E.	${\displaystyle \bigcup _{c>0}DTIME(2^{cn})}$	Solvable by a deterministic Turing machine in exponential time with a linear exponent.
ESPACE	${\displaystyle \bigcup _{c>0}DSPACE(2^{cn})}$	Solvable by a deterministic Turing machine in linear exponential space.
EXP		Another name for EXPTIME.
EXPSPACE	${\displaystyle \bigcup _{c>0}DSPACE(2^{n^{c}})}$	Solvable by a deterministic Turing machine in an exponential space.
EXPTIME	${\displaystyle \bigcup _{c>0}DTIME(2^{n^{c}})}$	Solvable by a deterministic Turing machine in exponential time.
FP		Functions that can be calculated in polynomial time.
FPT		Solvable by a parameterized algorithm (Fixed Parameter Tractable)
L.	${\displaystyle DSPACE(\log(n))}$	Can be solved by a Turing machine in logarithmic space.
LOGSPACE		Another name for L.
NC		Solvable in polylogarithmic time on a parallel register machine with many polynomial processors.
NE	${\displaystyle \bigcup _{c>0}NTIME(2^{cn})}$	Solvable by a nondeterministic Turing machine in linear exponential time.
NESPACE	${\displaystyle \bigcup _{c>0}NSPACE(2^{cn})}$	Solvable by a nondeterministic Turing machine on linear exponential space.
NEXP		Another name for NEXPTIME
NEXPSPACE	${\displaystyle \bigcup _{c>0}NSPACE(2^{n^{c}})}$	Solvable by a nondeterministic Turing machine on exponential space.
NEXPTIME	${\displaystyle \bigcup _{c>0}NTIME(2^{n^{c}})}$	Solvable by a nondeterministic Turing machine in exponential time.
NL	${\displaystyle \bigcup _{c>0}NSPACE(\log ^{c}(n))}$	Solvable by a nondeterministic Turing machine in logarithmic space.
NLOGSPACE		Another name for NL.
NP	${\displaystyle \bigcup _{c>0}NTIME(n^{c})}$	Solvable by a nondeterministic Turing machine in polynomial time.
NP-complete		The most difficult problems in NP.
NP-difficult		Problems to which all NP problems can be reduced in polynomial time.
NPSPACE	${\displaystyle \bigcup _{c>0}NSPACE(n^{c})}$	Solvable by a nondeterministic Turing machine on polynomial space. Corresponds to PSPACE.
NSPACE (f ( n ))		Solvable by a nondeterministic Turing machine in O (f ( n )) space.
NTIME (f ( n ))		Solvable by a nondeterministic Turing machine in O (f ( n )) time.
P	${\displaystyle \bigcup _{c>0}DTIME(n^{c})}$	Solvable in polynomial time by a deterministic Turing machine.
P-complete		The most difficult problems in P.
POLYKERNEL		Parameterized problems whose instances (I, k) have problem cores whose size is limited by a polynomial in k .
PH		The union of all classes in the polynomial time hierarchy .
PP		Solvable by a probabilistic Turing machine in polynomial time, the answer is correct in more than half of the cases.
PSPACE	${\displaystyle \bigcup _{c>0}DSPACE(n^{c})}$	Solvable by a deterministic Turing machine in polynomial space. (Corresponds to NPSPACE)
PSPACE complete		The toughest problems in PSPACE.
RL		Solvable by a probabilistic Turing machine in logarithmic space (“yes” answer is always, “no” answer is mostly correct).
RP		Solvable by a probabilistic Turing machine in polynomial time (“yes” answer is always, “no” answer is mostly correct).
SL		Problems that can be reduced to USTCON log-space. Corresponds to L.
W [n]		Problems from a Weft n can be solved switching power
W [n, h]		Problems that can be solved by a Weft n switching network with height h
ZPP		Problems that are probabilistic from an NTM with always the correct answer but U. can be solved in terms of duration that differ from the average case

Web links

• Complexity Zoo - List of complexity classes and their relationships with one another