Unary Encoding

computation

Definition

Unary Encoding

Unary encoding represents a non-negative integer $n$ by a string whose length is proportional to $n$ itself.

A common convention is $n\mapsto 1^n$, so $5$ is encoded as $11111$.

Length

Under unary encoding, the encoded length of $n$ is

$$|1^n|=n.$$

Thus the length of the representation is linear in the numeric value.

This contrasts with binary encoding, where the length of $n$ is $\Theta (\log n)$.

Complexity

Unary encoding is important in complexity theory because it removes the exponential gap between a number and its representation length.

If an algorithm loops over all values $0,1,\dots ,W$, then it performs $\Theta (W)$ iterations. Under unary encoding, the input already contains $\Theta (W)$ symbols for $W$, so such a loop is polynomial in the input length.

Under binary encoding, the same loop may be exponential in the input length, because $W$ can be exponential in $\log W$.

Example

Pseudo-polynomial dynamic programming

A knapsack dynamic programme with capacity $W$ often has running time $O(nW)$.

If $W$ is unary-encoded, then the input length already includes $\Theta (W)$ symbols. Hence $O(nW)$ is polynomial in the unary input length.

If $W$ is binary-encoded, then the input contains only $\Theta (\log W)$ bits for the capacity. Hence the same running time can be exponential in the encoded input length.