Instance size and polynomially related encodings

Let $I$ be a set of instances and let $\sigma :I\to \{0,1{\}}^{\ast }$ be an effective binary encoding. The size of an instance $x\in I$ with respect to $\sigma$ is the length of its codeword: $\mathrm{\mid }x{\mathrm{\mid }}_{\sigma }:=\mathrm{\mid }\sigma (x)\mathrm{\mid }\mathrm{.}$

If $\sigma ,\tau :I\to \{0,1{\}}^{\ast }$ are two effective encodings of the same instance set, they are polynomially related when there exist polynomials $p,q:\mathbb{N}\to \mathbb{N}$ such that for every $x\in I$, $\mathrm{\mid }\sigma (x)\mathrm{\mid }\le p(\mathrm{\mid }\tau (x)\mathrm{\mid })\text{and}\mathrm{\mid }\tau (x)\mathrm{\mid }\le q(\mathrm{\mid }\sigma (x)\mathrm{\mid })\mathrm{.}$

• Resource bounds are measured as functions of encoded input length, not of an abstract instance before encoding.

• Polynomially related encodings may differ substantially, but neither can blow up the other's lengths by more than a polynomial factor.