/
Complexity Classes

Complexity Classes

Dec 07, 2023

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:

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

Complexity Classes - Families and Types

Complexity Class FamilyComputational Problem TypeModel of ComputationResourceBoundComplexity Class TypeDiagram
DTIME(𝑓(𝑛))DECISIONDeterministic Turing MachineTime / Search-Space

𝑂(𝑓(𝑛))

  • P = DTIME(𝑝𝑜𝑙𝑦(𝑛))
  • EXPTIME = DTIME(2𝑝𝑜𝑙𝑦(𝑛))

NTIME(𝑓(𝑛))DECISIONNon-Deterministic Turing MachineTime / Search-Space𝑂(𝑓(𝑛))
  • NP = NTIME(𝑝𝑜𝑙𝑦(𝑛))
  • NEXPTIME = NTIME(2𝑝𝑜𝑙𝑦(𝑛))
DSPACE(𝑓(𝑛))DECISIONDeterministic Turing MachineMemory / Space𝑂(𝑓(𝑛))
  • L = DSPACE(𝑙𝑜𝑔(𝑛))
  • PSPACE = DSPACE(𝑝𝑜𝑙𝑦(𝑛))
  • EXPSPACE = DSPACE(2𝑝𝑜𝑙𝑦(𝑛))
NSPACE(𝑓(𝑛))DECISIONNon-Deterministic Turing MachineMemory / Space𝑂(𝑓(𝑛))
  • NL = NSPACE(𝑙𝑜𝑔(𝑛))
  • NPSPACE = NSPACE(𝑝𝑜𝑙𝑦(𝑛))
  • NEXPSPACE = NSPACE(2𝑝𝑜𝑙𝑦(𝑛))
PTIME(𝑓(𝑛))DECISIONProbabilistic Turing MachineTime / Search-Space𝑂(𝑓(𝑛))
  • BPP = PTIME(𝑝𝑜𝑙𝑦(𝑛))
QTIME(𝑓(𝑛))DECISIONQuantum Turing MachineTime / Search-Space𝑂(𝑓(𝑛))
  • BQP = QTIME(𝑝𝑜𝑙𝑦(𝑛))

Other