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 |
| FPNP |
The analogue of PNP 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 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 |
| 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 ½) |
| 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) |