Binary Instance Encoding

Definition

Binary Instance Encoding

A binary instance encoding is an instance encoding in which every non-negative numerical field $z$ is represented by its binary encoding. Its field length is

$${\ell }_2(z)=\max \left\{1,\lceil {\log }_2(z+1)\rceil \right\}.$$

If an instance $I$ has structural encoding length $s(I)$ and numerical fields $z_1,\dots ,z_k$, then a delimited binary encoding has length

$$|{\mathrm{enc}}_{\mathrm{bin}}(I)|=\Theta \left(s(I)+\sum _{j=1}^k{\ell }_2(z_j)\right).$$

Thus a value $z_j$ may be exponential in the length of its field. Binary instance encoding concerns how numbers are written; it is independent of whether the problem is an optimisation or decision problem. This contrasts with unary instance encoding.