Math 2.0

Computer science Definition

Complexity class

Builds on Decision problemFormal languageTuring machineTime complexitySpace complexity

Definition

Let Σ\Sigma be a finite alphabet. Fix a model of computation, such as deterministic or nondeterministic Turing machines. Fix a resource measure on it, such as time or space. Fix a set ℱ\mathcal{F} of functions ℕ→ℕ\N \to \N, the allowed bounds. The complexity class given by these data is the set of all languages L⊆Σ∗L \subseteq \Sigma^* with the following property. For some f∈ℱf \in \mathcal{F}, some machine of the model decides LL and uses at most f(n)f(n) units of the resource on every input of length nn.

Remarks

Example: take deterministic multitape Turing machines, the time measure, and ℱ={n↦cnk+c:c,k∈ℕ}\mathcal{F} = \set{n \mapsto c n^k + c : c, k \in \N}. The class obtained is P, the class of decision problems solvable in polynomial time.

Non-example: the set of all languages L⊆{0,1}∗L \subseteq \set{0,1}^* is not a complexity class in this sense for any bounds. It is uncountable, while there are only countably many machines, so it contains undecidable languages.

The word is also used more loosely. Classes defined by circuits, by oracles, by probabilistic or quantum machines, or by counting problems instead of decision problems are also called complexity classes.

Reading path

To understand this page from the ground up, read these 6 pages in order. The foundations come first.

Show the path as a graph
Decision problem, concept, no evidence levelDecision problemconceptFormal language, concept, no evidence levelFormal languageconceptSpace complexity, concept, no evidence levelSpace complexityconceptTime complexity, concept, no evidence levelTime complexityconceptTuring machine, concept, no evidence levelTuring machineconceptComplexity class, definition, no evidence levelComplexity classdefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Decision problem concept
  2. Formal language concept
  3. Space complexity concept
  4. Time complexity concept
  5. Turing machine concept
  6. Complexity class definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Complexity_class
About this page
Tag8WNXTV6KPG
URIm2://8WNXTV6KPG
Kinddefinition
WritingW0 stub
MSC68Q15
DefinesComplexity class
UsesDecision problem, Formal language, Turing machine, Time complexity, Space complexity
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.