154 Complexity — P
154.1 Overview
This module defines the complexity class \(\mathsf{P}\) of polynomial-time decidable languages over the binary alphabet, following Arora–Barak Definition 1.13, as the union over all degrees \(c\) of the classes \(\mathrm{DTIME}(n^c + 1)\); the \(+1\) padding keeps each component nonempty on the empty input, where a bound of \(n^c\) steps would vanish. The main results give membership criteria for \(\mathsf{P}\) from concrete polynomial bounds and certify that the padded definition coincides with the conventional reading: a language is in \(\mathsf{P}\) exactly when some machine decides it within \(C \cdot (n+1)^d\) steps for constants \(C\) and \(d\).
154.2 Declarations
The class \(\mathsf{P}\) of polynomial-time decidable languages over the binary alphabet: a language \(L \subseteq \{ 0,1\} ^{*}\) belongs to \(\mathsf{P}\) when there is a natural number \(c\) such that \(L \in \mathrm{DTIME}(n \mapsto n^c + 1)\), i.e. some deterministic finite Turing machine decides \(L\) within \(a \cdot (n^c + 1)\) steps on every input of length \(n\), for some constant \(a\). In symbols, \(\mathsf{P} = \bigcup _{c \in \mathbb {N}} \mathrm{DTIME}(n^c + 1)\).
For every natural number \(c\), the class \(\mathrm{DTIME}(n \mapsto n^c + 1)\) — the languages over \(\{ 0,1\} \) decided by some deterministic finite Turing machine within \(a \cdot (n^c + 1)\) steps on inputs of length \(n\), for some constant \(a\) — is contained in \(\mathsf{P}\).
Let \(L\) be a language over the binary alphabet, let \(T : \mathbb {N} \to \mathbb {N}\) be a time bound with \(L \in \mathrm{DTIME}(T)\), and let \(c\) and \(d\) be natural numbers such that \(T(n) \le c \cdot (n^d + 1)\) for every \(n\). Then \(L \in \mathsf{P}\). (The domination is required pointwise, at every input length, not merely for all sufficiently large \(n\).)
For all natural numbers \(n\) and \(d\),
A language \(L\) over the binary alphabet belongs to \(\mathsf{P}\) if and only if there exist natural numbers \(C\) and \(d\) and a deterministic finite Turing machine \(M\) over \(\{ 0,1\} \) such that \(M\) decides \(L\) within \(C \cdot (n + 1)^d\) steps on every input of length \(n\). In particular the \(+1\) padding in the definition of \(\mathsf{P}\) describes the same class as the conventional polynomial time bounds \(C \cdot (n+1)^d\).
Every language over the binary alphabet in \(\mathrm{DTIME}(n \mapsto 1)\) — that is, decided by some deterministic finite Turing machine within a constant number of steps, uniformly over all inputs — belongs to \(\mathsf{P}\).