153 Complexity — Model Invariance
153.1 Overview
This module records the model-invariance payoff of the Turing-machine robustness theorems, in the spirit of Arora–Barak §1.3.1 and §1.6.1 (“why the model may not matter”): the class \(\mathrm{DTIME}\) of binary languages is invariant under enlarging the tape alphabet, the alphabet-dependent constant being absorbed into \(\mathrm{DTIME}\)’s built-in constant factor, and the class \(\mathsf{P}\) is invariant both under enlarging the alphabet and under restricting to machines with a single work tape, since the quadratic slowdown of tape reduction preserves polynomial time bounds.
153.2 Declarations
Let \(\Gamma \) be an alphabet, let \(M\) be a deterministic finite Turing machine over \(\Gamma \), let \(e : \{ 0,1\} \hookrightarrow \Gamma \) be an injective embedding of the binary symbols into \(\Gamma \), let \(L \subseteq \{ 0,1\} ^{*}\) be a language over the binary alphabet, and let \(T : \mathbb {N} \to \mathbb {N}\) be a time bound. We say that \(M\) decides \(L\) via \(e\) within time \(T\) if for every binary string \(x\), when \(M\) is run on the input obtained by applying \(e\) to each symbol of \(x\), it halts within \(T(|x|)\) steps with output the one-symbol string \(e(b)\), where \(b \in \{ 0,1\} \) is the indicator of whether \(x \in L\).
Let \(\Gamma \) be a finite alphabet, let \(e : \{ 0,1\} \hookrightarrow \Gamma \) be an injective embedding of the binary symbols, let \(L \subseteq \{ 0,1\} ^{*}\) be a language over the binary alphabet, and let \(T : \mathbb {N} \to \mathbb {N}\) be a time bound. If some deterministic finite Turing machine over \(\Gamma \) decides \(L\) via \(e\) within time \(T\), then \(L \in \mathrm{DTIME}(n \mapsto T(n) + 1)\); that is, some deterministic finite Turing machine over the binary alphabet decides \(L\) within \(a \cdot (T(n) + 1)\) steps on every input of length \(n\), for some constant \(a\).
Let \(\Gamma \) be a finite alphabet, let \(e : \{ 0,1\} \hookrightarrow \Gamma \) be an injective embedding of the binary symbols, let \(L \subseteq \{ 0,1\} ^{*}\) be a language over the binary alphabet, and let \(C\) and \(d\) be natural numbers. If some deterministic finite Turing machine over \(\Gamma \) decides \(L\) via \(e\) within \(C \cdot (n+1)^d\) steps on every input of length \(n\), then \(L \in \mathsf{P}\). In particular, polynomial-time decidability over any finite alphabet already places a language in the binary-alphabet class \(\mathsf{P}\).
A language \(L\) over the binary alphabet belongs to \(\mathsf{P}\) if and only if there exist a deterministic finite Turing machine \(M\) over \(\{ 0,1\} \) and natural numbers \(C\) and \(d\) such that \(M\) has exactly one work tape and \(M\) decides \(L\) within \(C \cdot (n+1)^d\) steps on every input of length \(n\). Thus restricting to a single work tape does not change the class \(\mathsf{P}\): the quadratic overhead of tape reduction preserves polynomial time bounds.