Definition
Unary Instance Encoding
A unary instance encoding is an instance encoding in which every non-negative numerical field
is represented in unary, for example by the self-delimiting string . Its field length is If an instance
has structural encoding length and numerical fields , then this encoding has length 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.