A complexity class is a collection of computational problems that need roughly the same amount of a specified resource when solved by an algorithm. Typical resources are time (how many steps an algorithm uses) and space (how much memory it requires); other resources include randomness, parallelism, and circuit size. Complexity classes provide a coarse but powerful way to compare the inherent difficulty of problems under a chosen model of computation.

Formal idea

Formally, classes are defined relative to a computational model (most often a Turing machine) and an asymptotic resource bound. For example, P denotes the set of decision problems solvable in polynomial time by a deterministic Turing machine, while PSPACE contains problems solvable with polynomial space. Definitions typically use worst-case analysis and asymptotic notation so that classes capture behavior on large inputs rather than single instances.

Common classes and examples

  • P — efficient deterministic polynomial-time algorithms.
  • NP — problems whose solutions can be verified in polynomial time; includes many natural combinatorial problems.
  • co-NP, PSPACE, EXPTIME — larger classes defined by resource bounds or complements.
  • Randomized classes like BPP and RP, and space-bounded classes such as L and NL.

A central concept is reduction: one problem is at least as hard as another if instances can be transformed efficiently. Reductions lead to complete problems for a class (for example, many natural problems are NP-complete). The discovery of NP-completeness in the early 1970s showed how to classify broad families of difficult problems.

Role and significance

Complexity classes shape both theory and practice. They guide algorithm design, inform cryptographic assumptions, and identify when heuristic or approximate methods are necessary. Many foundational questions remain open, most famously whether P equals NP, which asks whether every problem whose solutions can be verified quickly can also be solved quickly.

Further notes

Complexity theory studies relationships among classes (hierarchies and separations) and closure properties under operations like complementation or oracle access. For introductions and surveys see resources in theoretical computer science overview, mathematical foundations background, and specialized material on reductions and completeness detailed survey.