Math 2.0

Computer science Definition

P

Builds on Complexity classMultitape Turing machineTime complexityFormal language

Definition

Let Σ\Sigma be a finite alphabet. Let t ⁣:ℕ→ℕt \colon \N \to \N be a function. The class DTIME(t)\mathrm{DTIME}(t) is the set of languages L⊆Σ∗L \subseteq \Sigma^* decided by some deterministic multitape Turing machine MM as follows. On every input of length nn, the machine MM halts within O(t(n))O(t(n)) steps. The complexity class P is P=⋃k∈ℕDTIME(nk).\mathrm{P} = \bigcup_{k \in \N} \mathrm{DTIME}(n^k). So L∈PL \in \mathrm{P} when some deterministic Turing machine decides LL with time complexity O(nk)O(n^k) for some kk.

Remarks

Example: the language of binary palindromes belongs to the class P, as follows. A two-tape machine copies the input to its work tape, moves the input head back to the start, and compares the input read forward with the copy read backward. This takes O(n)O(n) steps.

Non-example: a machine that solves a problem by testing all 2n2^n subsets of an nn-element set uses about 2n2^n steps, and 2n2^n is not O(nk)O(n^k) for any kk. Such a machine does not show that its problem is in P, though a faster algorithm might exist.

The class is the same for one-tape and multitape machines, since a one-tape machine simulates tt steps of a multitape machine in O(t2)O(t^2) steps. P is closed under union, intersection, complement and concatenation of languages.

Reading path

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

Show the path as a graph
Complexity class, concept, no evidence levelComplexity classconceptFormal language, concept, no evidence levelFormal languageconceptMultitape Turing machine, concept, no evidence levelMultitape Turing mach…conceptTime complexity, concept, no evidence levelTime complexityconceptP, definition, no evidence levelPdefinition
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. Complexity class concept
  2. Formal language concept
  3. Multitape Turing machine concept
  4. Time complexity concept
  5. P definition

Further reading

  1. Web https://en.wikipedia.org/wiki/P_(complexity)
About this page
TagXV9VDFVK6Y
URIm2://XV9VDFVK6Y
Kinddefinition
WritingW0 stub
MSC68Q15
DefinesP
UsesComplexity class, Multitape Turing machine, Time complexity, Formal language
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • 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.