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. | Solvable by a deterministic Turing machine in exponential time with a linear exponent. | ||
ESPACE | Solvable by a deterministic Turing machine in linear exponential space. | ||
EXP | Another name for EXPTIME. | ||
EXPSPACE | Solvable by a deterministic Turing machine in an exponential space. | ||
EXPTIME | 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. | 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 | Solvable by a nondeterministic Turing machine in linear exponential time. | ||
NESPACE | Solvable by a nondeterministic Turing machine on linear exponential space. | ||
NEXP | Another name for NEXPTIME | ||
NEXPSPACE | Solvable by a nondeterministic Turing machine on exponential space. | ||
NEXPTIME | Solvable by a nondeterministic Turing machine in exponential time. | ||
NL | Solvable by a nondeterministic Turing machine in logarithmic space. | ||
NLOGSPACE | Another name for NL. | ||
NP | 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 | 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 | 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 | 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