Polynomially related encodings preserve polynomial-time and polynomial-space classes

Assume $L$ is decidable in polynomial time under $\tau$. Let $M_{\tau }$ be a decider for the code language $\tau [L]$ whose running time is polynomial in the input length. On an arbitrary binary input $z$, first run the assumed polynomial-time decider for the valid-code language $\sigma [I]$. If $z\mathrm{\notin }\sigma [I]$, reject. If $z=\sigma (x)$ is valid, compute $T_{\sigma \to \tau }(z)$ and run $M_{\tau }$ on that translated word. The output is correct because $T_{\sigma \to \tau }(\sigma (x))=\tau (x)$. By [L1] and [L2], the translated length is polynomially bounded in $\mathrm{\mid }z\mathrm{\mid }$, and the validity test and translator are polynomial-time by hypothesis, so the whole composition is polynomial-time.

The same composition argument works in the opposite direction using the validity test for $\tau [I]$ and the translator $T_{\tau \to \sigma }$. Therefore polynomial-time decidability under $\sigma$ and under $\tau$ are equivalent.

Replace the time bounds in step 1.1 by space bounds. The validity tests and translators use polynomial space by hypothesis, and [L1] again converts a polynomial bound in one encoding length into a polynomial bound in the other. Hence polynomial-space decidability is preserved in both directions as well.

Steps 2.1 and 2.2 prove the preservation of polynomial-time and polynomial-space classes described in [L3].