200 Complexity — Poly Time Pairing
200.1 Overview
This module proves closure properties of the class \(\mathrm{FP}\) of polynomial-time computable functions on bit strings [AB09, ch. 2] that are needed when a reduction must keep its input while computing from it: constant functions and prepending a fixed word, the threaded payload map on pairs, pairing of two polynomial-time functions through the self-delimiting pair encoding \(\langle a,b\rangle \), the total pair projections and their rearrangements, concatenation, Boolean branching and conjunction, length tests on pairs, and the unary maps \(x \mapsto 1^{|x|}\) and \(x \mapsto 1^{C(|x|+1)^d}\) (the input of a uniformity machine [AB09, Def. 6.12]). All of them are assembled from a catalog of explicit finite Turing-machine constructions.
200.2 Declarations
Let \(f\) be a function from bit strings to bit strings. If there are a finite binary Turing machine \(M\) and a constant \(a \in \mathbb {N}\) such that \(M\) computes \(f\) within \(a(n+1)\) steps on every input of length \(n\), then \(f\) is polynomial-time computable, i.e. some finite binary Turing machine computes \(f\) within \(C(n+1)^c\) steps on every input of length \(n\), for some constants \(C, c \in \mathbb {N}\).
For every fixed bit string \(w\), the constant function \(x \mapsto w\) on bit strings 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 \(g\) be a function from bit strings to bit strings, and let \(\langle a,b\rangle \) denote the self-delimiting pair encoding of bit strings \(a\) and \(b\) (every bit of \(a\) doubled, then \(01\), then \(b\)). The threaded payload map of \(g\) sends a bit string \(z\) to \(\langle a, g(b)\rangle \) when \(z = \langle a,b\rangle \) is a pair encoding, carrying the first component unchanged, and to the empty word when \(z\) is not of this form.
Let \(g\) be a function from bit strings to bit strings, let \(\langle a,b\rangle \) denote the self-delimiting pair encoding of bit strings \(a,b\) (every bit of \(a\) doubled, then \(01\), then \(b\)), and let \(\sigma _g\) be the threaded payload map of \(g\), which decodes a bit string \(z\) as a pair \(\langle a,b\rangle \) and outputs \(\langle a, g(b)\rangle \), or outputs the empty word if \(z\) is not a pair encoding. Then \(\sigma _g(\langle a,b\rangle ) = \langle a, g(b)\rangle \) for all bit strings \(a\) and \(b\).
Let \(g\) be a polynomial-time computable function on bit strings (computed by some finite binary Turing machine within \(C(n+1)^c\) steps on inputs of length \(n\), for some constants \(C, c\)). Then its threaded payload map, which sends a pair encoding \(\langle a,b\rangle \) (every bit of \(a\) doubled, then \(01\), then \(b\)) to \(\langle a, g(b)\rangle \) and every bit string that is not a pair encoding to the empty word, is also polynomial-time computable.
Let \(\langle a,b\rangle \) denote the self-delimiting pair encoding of bit strings \(a\) and \(b\) (every bit of \(a\) doubled, then \(01\), then \(b\)). For all bit strings \(a, b, c\), appending \(c\) to \(\langle a,b\rangle \) appends it to the second component: \(\langle a,b\rangle \, c = \langle a, b\, c\rangle \), where juxtaposition denotes concatenation.
Let \(f\) and \(g\) be polynomial-time computable functions on bit strings (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 map \(x \mapsto \langle f(x), g(x)\rangle \) is polynomial-time computable, where \(\langle a,b\rangle \) denotes the self-delimiting pair encoding of bit strings \(a\) and \(b\) (every bit of \(a\) doubled, then \(01\), then \(b\)).
For a bit string \(v\), let \(\mathrm{split}(v)\) be the prefix of \(v\) preceding its last occurrence of \(1\), undefined when \(v\) contains no \(1\). Then for every \(n \in \mathbb {N}\), \(\mathrm{split}(1^{n+1})\) is defined and equals \(1^n\), where \(1^k\) is the word of \(k\) ones.
The map sending a bit string \(x\) to the word \(1^{|x|}\) of \(|x|\) ones 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 \(f\) and \(g\) be polynomial-time computable functions on bit strings (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 map \(x \mapsto f(x)\, g(x)\), sending \(x\) to the concatenation of \(f(x)\) and \(g(x)\), is polynomial-time computable.
For all \(C, d \in \mathbb {N}\), the map sending a bit string \(x\) to the word \(1^{C(|x|+1)^d}\) of \(C(|x|+1)^d\) ones is polynomial-time computable, i.e. some finite binary Turing machine computes it within \(K(n+1)^k\) steps on every input of length \(n\), for some constants \(K, k \in \mathbb {N}\).
For every fixed bit string \(w\), the map \(x \mapsto w\, x\) that prepends \(w\) to a bit string \(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 \(\langle a,b\rangle \) denote the self-delimiting pair encoding of bit strings \(a\) and \(b\) (every bit of \(a\) doubled, then \(01\), then \(b\)). The total first projection \(\pi _1\) sends a bit string \(z\) to \(a\) when \(z = \langle a,b\rangle \) is a pair encoding, and to the empty word when \(z\) is not of this form.
Let \(\langle a,b\rangle \) denote the self-delimiting pair encoding of bit strings \(a\) and \(b\) (every bit of \(a\) doubled, then \(01\), then \(b\)). The total second projection \(\pi _2\) sends a bit string \(z\) to \(b\) when \(z = \langle a,b\rangle \) is a pair encoding, and to the empty word when \(z\) is not of this form.
Let \(\langle a,b\rangle \) denote the self-delimiting pair encoding of bit strings \(a\) and \(b\) (every bit of \(a\) doubled, then \(01\), then \(b\)), and let \(\pi _1\) be the total first projection, which returns the first component of a pair encoding and the empty word on any other bit string. Then \(\pi _1(\langle a,b\rangle ) = a\) for all bit strings \(a, b\).
Let \(\langle a,b\rangle \) denote the self-delimiting pair encoding of bit strings \(a\) and \(b\) (every bit of \(a\) doubled, then \(01\), then \(b\)), and let \(\pi _2\) be the total second projection, which returns the second component of a pair encoding and the empty word on any other bit string. Then \(\pi _2(\langle a,b\rangle ) = b\) for all bit strings \(a, b\).
Let \(\pi _1\) be the total first projection, which sends 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 any other bit string to the empty word. Then for every bit string \(z\), \(|\pi _1(z)| \le |z|\).
The total first projection \(\pi _1\), which sends 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 any other bit string to the empty word, 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}\).
The total second projection \(\pi _2\), which sends 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 \(b\) and any other bit string to the empty word, 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 \(\pi _1\) be the total first projection, which sends 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 any other bit string to the empty word. For every \(n \in \mathbb {N}\), the \(n\)-fold iterate \(\pi _1^{n} = \pi _1 \circ \cdots \circ \pi _1\) (the identity for \(n = 0\)), which extracts the root of a left-nested tuple, is polynomial-time computable.
Let \(\pi _1\) and \(\pi _2\) be the total projections, 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 any other bit string to the empty word. Then the map \(z \mapsto \pi _1(z)\, \pi _2(z)\), sending \(z\) to the concatenation of its two components, is polynomial-time computable.
Let \(\langle a,b\rangle \) denote the self-delimiting pair encoding of bit strings \(a\) and \(b\) (every bit of \(a\) doubled, then \(01\), then \(b\)), and let \(\pi _1\) and \(\pi _2\) be the total projections, which send \(\langle a,b\rangle \) to \(a\) and to \(b\) respectively, and any bit string that is not a pair encoding to the empty word. Then the map \(z \mapsto \langle \pi _2(z), \pi _1(z)\rangle \) is polynomial-time computable.
Let \(p\) be a Boolean-valued predicate on bit strings and let \(f, g\) be functions from bit strings to bit strings. Suppose that the map sending \(x\) to the one-bit word \(p(x)\) is polynomial-time computable, and that \(f\) and \(g\) are polynomial-time computable (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 map sending \(x\) to \(f(x)\) if \(p(x)\) is true and to \(g(x)\) otherwise is polynomial-time computable.
Let \(p\) and \(q\) be Boolean-valued predicates on bit strings such that the maps sending \(x\) to the one-bit words \(p(x)\) and \(q(x)\) are both 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 map sending \(x\) to the one-bit word \(p(x) \land q(x)\) is polynomial-time computable.
Let \(\pi _1\) and \(\pi _2\) be the total projections, 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 any other bit string to the empty word. Then the map sending a bit string \(z\) to the one-bit word that is \(1\) if \(|\pi _2(z)| \le |\pi _1(z)|\) 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 \(\pi _1\) and \(\pi _2\) be the total projections, 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 any other bit string to the empty word. Then the map sending a bit string \(z\) to the one-bit word that is \(1\) if \(|\pi _1(z)| = |\pi _2(z)|\) 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}\).