Unary Instance Encoding

Definition

Unary Instance Encoding

A unary instance encoding is an instance encoding in which every non-negative numerical field $z$ is represented in unary, for example by the self-delimiting string $1^{z}0$. Its field length is

$${\ell }_1(z)=z+1.$$

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

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

Each numerical magnitude is therefore at most linear in its encoded field length. An algorithm polynomial in these magnitudes may consequently be polynomial under unary encoding even when it is only pseudo-polynomial under binary instance encoding.