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.See computation for a chart showing which classes are subsets of other classes.
Many of these classes have a 'Co' partner which consists of the complements of all languages in the original class. For example if 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.)
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 |
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 |
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 |
FP^{NP} | The analogue of P^{NP} for function problems; the home of the traveling salesman problem |
IP | Solvable in polynomial time by an interactive proof system |
MA | Solvable in polynomial time by an 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 |
NP | YES answers checkable in polynomial time (see complexity classes P and NP) |
NP-complete | The hardest problems in NP |
NP-easy | Analogue to P^{NP} for function problems; another name for FP^{NP} |
NP-equivalent | The hardest problems in FP^{NP} |
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 |
PCP | Probabilistically Checkable Proof |
PH | The union of the classes in the polynomial hierarchy |
P^{NP} | Solvable in polynomial time with an oracle for a problem in NP; also known as Δ_{2}P |
PP | Probabilistically Polynomial (answer is right with probability slightly more than ½) |
PSPACE | Solvable with polynomial memory and unlimited time |
PSPACE-complete | The hardest problems in PSPACE |
RP | Solvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right) |
UP | Unambiguous Non-Deterministic Polytime functions. |
ZPP | Solvable by randomized algorithms (answer is always right, average running time is polynomial) |
External link
- Complexity Zoo - list of 396 complexity classes (as of May 2004) and their properties