[proofplan] We decide membership in $A$ under the second encoding by first using the validity test for $\operatorname{enc}_2(\mathcal{C})$, then translating valid inputs from $\operatorname{enc}_2$ to $\operatorname{enc}_1$, and finally running the polynomial-time decider for the first encoded language. The validity test and translator are exactly the one-directional polynomial-relatedness hypotheses stated in the theorem. The only remaining runtime point is that the translated string has polynomial length in the original input length, which follows because a Turing machine running for polynomially many steps can write only polynomially many output symbols. Composing the validity, translation, and decision bounds gives a polynomial total running time. [/proofplan] [step:Choose polynomial time bounds for the validity test, the translator, and the first decider] Let $L_1 := \{\operatorname{enc}_1(c) : c \in A\} \subseteq \Sigma_1^*$ and $L_2 := \{\operatorname{enc}_2(c) : c \in A\} \subseteq \Sigma_2^*$ denote the encoded languages, where the finite alphabets $\Sigma_1$ and $\Sigma_2$ and the maps $\operatorname{enc}_1: \mathcal{C} \to \Sigma_1^*$ and $\operatorname{enc}_2: \mathcal{C} \to \Sigma_2^*$ are those declared in the theorem statement. Since $\operatorname{enc}_1$ and $\operatorname{enc}_2$ are injective encodings, each encoded string represents at most one object of $\mathcal{C}$. We now unpack the one-directional polynomial-relatedness assumption from the theorem statement. First, there exists a deterministic Turing machine $V_2: \Sigma_2^* \to \{0,1\}$ and a polynomial $r: \mathbb{N} \to \mathbb{N}$ such that, for every $w \in \Sigma_2^*$, the machine $V_2$ halts on input $w$ within $r(|w|)$ steps and accepts exactly when $w \in \operatorname{enc}_2(\mathcal{C})$. Second, there exists a deterministic Turing machine $T_{2 \to 1}: \Sigma_2^* \to \Sigma_1^*$ and a polynomial $p: \mathbb{N} \to \mathbb{N}$ such that, for every $w \in \Sigma_2^*$, the machine $T_{2 \to 1}$ halts on input $w$ within $p(|w|)$ steps, and for every $c \in \mathcal{C}$ it satisfies $T_{2 \to 1}(\operatorname{enc}_2(c)) = \operatorname{enc}_1(c)$. Since $L_1$ is decidable in polynomial time, there exists a deterministic Turing machine $M_1: \Sigma_1^* \to \{0,1\}$ and a polynomial $q: \mathbb{N} \to \mathbb{N}$ such that, for every $u \in \Sigma_1^*$, the machine $M_1$ halts on input $u$ within $q(|u|)$ steps and accepts exactly when $u \in L_1$. Replacing $p$, $q$, and $r$ by larger polynomials if necessary, we may assume that all three are nondecreasing and that each is at least $1$ on $\mathbb{N}$. This does not change the polynomial-time hypotheses. [/step] [step:Build the decider for the second encoding by validating and then translating] Define a deterministic Turing machine $M_2: \Sigma_2^* \to \{0,1\}$ as follows. On input $w \in \Sigma_2^*$, the machine first runs $V_2$ on $w$. If $V_2$ rejects, then $M_2$ rejects. If $V_2$ accepts, then $w \in \operatorname{enc}_2(\mathcal{C})$, so there exists $c \in \mathcal{C}$ with $w = \operatorname{enc}_2(c)$. The machine then runs $T_{2 \to 1}$ on $w$, lets $u \in \Sigma_1^*$ denote the output string, runs $M_1$ on $u$, and returns the same accept or reject answer. If $w \notin \operatorname{enc}_2(\mathcal{C})$, then $w \notin L_2$ by the definition of $L_2$, and $M_2$ rejects. If $w = \operatorname{enc}_2(c)$ for some $c \in \mathcal{C}$, then the translation hypothesis gives \begin{align*} u = T_{2 \to 1}(w) = \operatorname{enc}_1(c). \end{align*} Since $M_1$ decides $L_1$, we have \begin{align*} M_2(w) = 1 \iff M_1(u) = 1 \iff u \in L_1. \end{align*} Because $u = \operatorname{enc}_1(c)$ and $\operatorname{enc}_1$ is injective, membership in $L_1$ is equivalent to membership of the represented object in $A$: \begin{align*} \operatorname{enc}_1(c) \in L_1 \iff \exists d \in A \text{ such that } \operatorname{enc}_1(d) = \operatorname{enc}_1(c) \iff c \in A. \end{align*} Similarly, because $w = \operatorname{enc}_2(c)$ and $\operatorname{enc}_2$ is injective, \begin{align*} w \in L_2 \iff c \in A. \end{align*} Combining these equivalences gives \begin{align*} M_2(w) = 1 \iff w \in L_2. \end{align*} Thus $M_2$ decides $L_2$ on every input in $\Sigma_2^*$. [guided] The construction must handle every string in $\Sigma_2^*$, not only strings that are known in advance to encode objects. Define the machine $M_2: \Sigma_2^* \to \{0,1\}$ in two stages. On input $w \in \Sigma_2^*$, first run the validity recognizer $V_2: \Sigma_2^* \to \{0,1\}$. If $V_2$ rejects, then $w \notin \operatorname{enc}_2(\mathcal{C})$, hence $w \notin L_2 = \{\operatorname{enc}_2(c) : c \in A\}$, so $M_2$ rejects. It remains to consider the case where $V_2$ accepts. Then $w \in \operatorname{enc}_2(\mathcal{C})$, so there exists $c \in \mathcal{C}$ such that $w = \operatorname{enc}_2(c)$. Now run the translator $T_{2 \to 1}: \Sigma_2^* \to \Sigma_1^*$ on $w$ and write its output as $u \in \Sigma_1^*$. The translator is correct on encoded inputs, hence \begin{align*} u = T_{2 \to 1}(\operatorname{enc}_2(c)) = \operatorname{enc}_1(c). \end{align*} Then run the decider $M_1: \Sigma_1^* \to \{0,1\}$ on $u$ and output whatever $M_1$ outputs. Since $M_1$ decides $L_1$, it accepts $u$ exactly when $u \in L_1$. We now translate this language statement back into a statement about the object $c$. Because $u = \operatorname{enc}_1(c)$ and $L_1 = \{\operatorname{enc}_1(d) : d \in A\}$, \begin{align*} u \in L_1 \iff \exists d \in A \text{ such that } \operatorname{enc}_1(d) = \operatorname{enc}_1(c). \end{align*} The injectivity of $\operatorname{enc}_1$ implies that $\operatorname{enc}_1(d) = \operatorname{enc}_1(c)$ holds exactly when $d = c$. Hence \begin{align*} u \in L_1 \iff c \in A. \end{align*} The same point must be checked for the second encoding. Since $w = \operatorname{enc}_2(c)$ and $L_2 = \{\operatorname{enc}_2(d) : d \in A\}$, injectivity of $\operatorname{enc}_2$ gives \begin{align*} w \in L_2 \iff c \in A. \end{align*} Therefore \begin{align*} M_2(w) = 1 \iff u \in L_1 \iff c \in A \iff w \in L_2. \end{align*} Combining the invalid-input case with the valid-input case proves that $M_2$ decides $L_2$ as a language over all of $\Sigma_2^*$. [/guided] [/step] [step:Bound the translated input length by the translation time] Let $w \in \Sigma_2^*$ be an input accepted by $V_2$, and set \begin{align*} n := |w|. \end{align*} Since $V_2$ accepts exactly $\operatorname{enc}_2(\mathcal{C})$, there exists $c \in \mathcal{C}$ such that $w = \operatorname{enc}_2(c)$. The translator $T_{2 \to 1}$ halts on $w$ within $p(n)$ steps. Under the standard single-tape output convention, one computation step writes at most one output symbol; under any fixed finite-tape model this changes the bound only by a machine-dependent constant factor. Absorbing that constant into $p$, the length of the output satisfies \begin{align*} |T_{2 \to 1}(w)| \leq p(n). \end{align*} Since $T_{2 \to 1}(w) = \operatorname{enc}_1(c)$, we obtain \begin{align*} |\operatorname{enc}_1(c)| \leq p(n). \end{align*} [/step] [step:Compose the polynomial bounds to obtain polynomial running time on every input] Let $w \in \Sigma_2^*$ have length $n$. The validity stage takes at most $r(n)$ steps. If $V_2$ rejects, then $M_2$ halts after this stage. If $V_2$ accepts, then the translation stage takes at most $p(n)$ steps, and the second decision stage runs $M_1$ on a string $u \in \Sigma_1^*$ with $|u| \leq p(n)$. Since $q$ is nondecreasing, \begin{align*} q(|u|) \leq q(p(n)). \end{align*} Therefore the total running time of $M_2$ on every input $w \in \Sigma_2^*$ is at most \begin{align*} r(n) + p(n) + q(p(n)). \end{align*} Because $p$, $q$, and $r$ are polynomials, the function $n \mapsto r(n) + p(n) + q(p(n))$ is also a polynomial bound. Thus $M_2$ decides $L_2$ in polynomial time. This proves that polynomial-time decidability of $A$ is preserved when passing from $\operatorname{enc}_1$ to the polynomially related encoding $\operatorname{enc}_2$. [guided] Let $w \in \Sigma_2^*$ be any input and define its length by $n := |w|$. The validity stage runs $V_2$ on $w$, and the polynomial-relatedness hypothesis gives the bound $r(n)$ for this stage. If $V_2$ rejects, the machine $M_2$ stops immediately, so the running time is at most $r(n)$. Suppose instead that $V_2$ accepts. Then $M_2$ runs the translator $T_{2 \to 1}$, whose running time is at most $p(n)$. Let $u \in \Sigma_1^*$ denote the output of this translation. The previous length estimate gives $|u| \leq p(n)$. Since $M_1$ runs in time at most $q(m)$ on inputs of length $m$ and since $q$ was chosen nondecreasing, the final decision stage takes at most \begin{align*} q(|u|) \leq q(p(n)). \end{align*} Therefore every accepting-validity branch of $M_2$ has total running time at most \begin{align*} r(n) + p(n) + q(p(n)). \end{align*} The composition $q \circ p: \mathbb{N} \to \mathbb{N}$ is a polynomial because both $p$ and $q$ are polynomials, and the sum of finitely many polynomials is again a polynomial. Hence $n \mapsto r(n) + p(n) + q(p(n))$ is a polynomial bound for $M_2$ on all inputs. Together with the correctness proved above, this shows that $L_2$ is decidable in polynomial time. [/guided] [/step]