Instance Encoding

Definition

Instance Encoding

Let $\mathcal{I}$ be an instance space and $\Sigma$ a finite alphabet. An instance encoding is an injective, computable map

$$\mathrm{enc}:\mathcal{I}\to {\Sigma }^{\ast }$$

together with a computable decoder defined on its image such that

$$\mathrm{dec}(\mathrm{enc}(I))=I(I\in \mathcal{I}).$$

The problem instance supplied to a machine is the finite string $\mathrm{enc}(I)$, and its encoded length is

$$|I{|}_{\mathrm{enc}}=|\mathrm{enc}(I)|.$$

Time complexity is measured against this length. Different encodings may therefore change a complexity bound, although polynomially related encodings preserve polynomial-time solvability.