198 Complexity — P Closure
198.1 Overview
This module establishes the closure properties of the class \(\mathsf{P}\) [AB09, Def. 1.13] that are used tacitly throughout [AB09]: a language is in \(\mathsf{P}\) exactly when its one-bit indicator is polynomial-time computable, and \(\mathsf{P}\) is closed under polynomial-time preimages (many-one reductions), under intersection and union, and hence under arbitrary Boolean functions of finitely many tests. As applications, comparing the lengths of the two components of a pair, or of the outputs of two polynomial-time functions, is decidable in polynomial time.
198.2 Declarations
Let \(V \subseteq \{ 0,1\} ^*\) be a language and let \(\mathbf{1}_V(x) \in \{ 0,1\} \) be its indicator bit, equal to \(1\) if \(x \in V\) and \(0\) otherwise. Then \(V\) belongs to \(\mathsf{P}\), the class of languages decidable by a deterministic Turing machine in polynomial time, if and only if the map sending a bit string \(x\) to the one-bit word \(\mathbf{1}_V(x)\) is polynomial-time computable, i.e. some finite binary Turing machine computes it within \(C(n+1)^c\) steps on every input of length \(n\), for some constants \(C, c \in \mathbb {N}\).
Let \(V \subseteq \{ 0,1\} ^*\) be a language in \(\mathsf{P}\), the class of languages decidable by a deterministic Turing machine in polynomial time, and let \(g : \{ 0,1\} ^* \to \{ 0,1\} ^*\) be polynomial-time computable (computed by some finite binary Turing machine within \(C(n+1)^c\) steps on inputs of length \(n\), for some constants \(C, c\)). Then the preimage \(g^{-1}(V) = \{ x \in \{ 0,1\} ^* : g(x) \in V\} \) also belongs to \(\mathsf{P}\).
Let \(b : \{ 0,1\} ^* \to \{ 0,1\} \) be a Boolean test on bit strings such that the map sending \(z\) to the one-bit word \(b(z)\) is polynomial-time computable (computed by some finite binary Turing machine within \(C(n+1)^c\) steps on inputs of length \(n\), for some constants \(C, c\)). Then the language \(\{ z \in \{ 0,1\} ^* : b(z) = 1\} \) belongs to \(\mathsf{P}\), the class of languages decidable by a deterministic Turing machine in polynomial time.
Let \(L \subseteq \{ 0,1\} ^*\) be a language in \(\mathsf{P}\), the class of languages decidable by a deterministic Turing machine in polynomial time. Then the map sending a bit string \(z\) to the one-bit word \(\mathbf{1}_L(z)\), which is \(1\) if \(z \in L\) and \(0\) otherwise, is polynomial-time computable, i.e. some finite binary Turing machine computes it within \(C(n+1)^c\) steps on every input of length \(n\), for some constants \(C, c \in \mathbb {N}\).
Let \(L_1, L_2 \subseteq \{ 0,1\} ^*\) be languages in \(\mathsf{P}\), the class of languages decidable by a deterministic Turing machine in polynomial time. Then their intersection \(L_1 \cap L_2 = \{ z : z \in L_1 \text{ and } z \in L_2\} \) also belongs to \(\mathsf{P}\).
Let \(L_1, L_2 \subseteq \{ 0,1\} ^*\) be languages in \(\mathsf{P}\), the class of languages decidable by a deterministic Turing machine in polynomial time. Then their union \(L_1 \cup L_2 = \{ z : z \in L_1 \text{ or } z \in L_2\} \) also belongs to \(\mathsf{P}\).
Let \(\mathsf{P}\) be the class of languages over \(\{ 0,1\} \) decidable by a deterministic Turing machine in polynomial time. Then the empty language \(\emptyset \subseteq \{ 0,1\} ^*\) belongs to \(\mathsf{P}\).
Let \(\mathsf{P}\) be the class of languages over \(\{ 0,1\} \) decidable by a deterministic Turing machine in polynomial time. Then the language \(\{ 0,1\} ^*\) consisting of all bit strings belongs to \(\mathsf{P}\).
Let \(\iota \) be a finite index set and, for each \(i \in \iota \), let \(b_i : \{ 0,1\} ^* \to \{ 0,1\} \) be a Boolean test on bit strings such that the language \(\{ z : b_i(z) = 1\} \) belongs to \(\mathsf{P}\), the class of languages decidable by a deterministic Turing machine in polynomial time. Then for every Boolean function \(F : \{ 0,1\} ^{\iota } \to \{ 0,1\} \), the language
also belongs to \(\mathsf{P}\).
Let \(\pi _1\) and \(\pi _2\) be the total projections on bit strings, which send a bit string of the form \(\langle a,b\rangle \) (the self-delimiting pair encoding: every bit of \(a\) doubled, then \(01\), then \(b\)) to \(a\) and to \(b\) respectively, and send every other bit string to the empty word. Then the language \(\{ z \in \{ 0,1\} ^* : |\pi _1(z)| = |\pi _2(z)|\} \) belongs to \(\mathsf{P}\), the class of languages decidable by a deterministic Turing machine in polynomial time.
Let \(\pi _1\) and \(\pi _2\) be the total projections on bit strings, which send a bit string of the form \(\langle a,b\rangle \) (the self-delimiting pair encoding: every bit of \(a\) doubled, then \(01\), then \(b\)) to \(a\) and to \(b\) respectively, and send every other bit string to the empty word. Then the language \(\{ z \in \{ 0,1\} ^* : |\pi _2(z)| \le |\pi _1(z)|\} \) belongs to \(\mathsf{P}\), the class of languages decidable by a deterministic Turing machine in polynomial time.
Let \(f, g : \{ 0,1\} ^* \to \{ 0,1\} ^*\) be polynomial-time computable functions (each computed by some finite binary Turing machine within \(C(n+1)^c\) steps on inputs of length \(n\), for some constants \(C, c\)). Then the language \(\{ z \in \{ 0,1\} ^* : |f(z)| = |g(z)|\} \) belongs to \(\mathsf{P}\), the class of languages decidable by a deterministic Turing machine in polynomial time.
Let \(f, g : \{ 0,1\} ^* \to \{ 0,1\} ^*\) be polynomial-time computable functions (each computed by some finite binary Turing machine within \(C(n+1)^c\) steps on inputs of length \(n\), for some constants \(C, c\)). Then the language \(\{ z \in \{ 0,1\} ^* : |g(z)| \le |f(z)|\} \) belongs to \(\mathsf{P}\), the class of languages decidable by a deterministic Turing machine in polynomial time.