Complexity Classes

a complexity class contains a set of problems that take a similar range of time and space to solve
for example, a problem that belongs in the NP complexity class but not in the P complexity class CANNOT be solved with any algorithm whose time complexity is polynomial-time bounded

Complexity Classes - Components

A complexity class is defined by the following components:

Type of Computational Problem - e.g. decision problems, optimization problems, etc
Model of Computation - e.g. Deterministic Turing Machine, Non-Deterministic Turing Machine, etc
Bounded Resource Type(s) - either TIME or MEMORY/SPACE
Bound(s) - a specified asymptotic complexity (e.g. linear, polynomial, exponential, etc)

Complexity Classes - Families and Types

Complexity Class Family	Computational Problem Type	Model of Computation	Resource	Bound	Complexity Class Type	Diagram
DTIME(𝑓(𝑛))	DECISION	Deterministic Turing Machine	Time / Search-Space	𝑂(𝑓(𝑛))	P = DTIME(𝑝𝑜𝑙𝑦(𝑛)) EXPTIME = DTIME(2^{𝑝𝑜𝑙𝑦(𝑛)})
NTIME(𝑓(𝑛))	DECISION	Non-Deterministic Turing Machine	Time / Search-Space	𝑂(𝑓(𝑛))	NP = NTIME(𝑝𝑜𝑙𝑦(𝑛)) NEXPTIME = NTIME(2^{𝑝𝑜𝑙𝑦(𝑛)})
DSPACE(𝑓(𝑛))	DECISION	Deterministic Turing Machine	Memory / Space	𝑂(𝑓(𝑛))	L = DSPACE(𝑙𝑜𝑔(𝑛)) PSPACE = DSPACE(𝑝𝑜𝑙𝑦(𝑛)) EXPSPACE = DSPACE(2^{𝑝𝑜𝑙𝑦(𝑛)})
NSPACE(𝑓(𝑛))	DECISION	Non-Deterministic Turing Machine	Memory / Space	𝑂(𝑓(𝑛))	NL = NSPACE(𝑙𝑜𝑔(𝑛)) NPSPACE = NSPACE(𝑝𝑜𝑙𝑦(𝑛)) NEXPSPACE = NSPACE(2^{𝑝𝑜𝑙𝑦(𝑛)})
PTIME(𝑓(𝑛))	DECISION	Probabilistic Turing Machine	Time / Search-Space	𝑂(𝑓(𝑛))	BPP = PTIME(𝑝𝑜𝑙𝑦(𝑛))
QTIME(𝑓(𝑛))	DECISION	Quantum Turing Machine	Time / Search-Space	𝑂(𝑓(𝑛))	BQP = QTIME(𝑝𝑜𝑙𝑦(𝑛))

Other