Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
List of complexity classes
Main Page | See live article | Alphabetical index

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
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)

External link