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
|
| FPT | Fixed-parameter tractable
|
| IP | Solvable in polynomial time by an interactive proof system
|
| L | Solvable in logarithmic (small) space
|
| 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
|
| 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
|
| 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
|
| 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)
|
