Polynomially Related Encoding

complexity-theory

Definition

Polynomially Related Encoding

Two encodings $e_1$ and $e_2$ of the same class of problem instances are polynomially related if their encoded lengths bound each other by fixed polynomials.

Formally, there exist polynomials $p$ and $q$ such that, for every instance $I$,

$$|e_1(I)|\le p(|e_2(I)|)\text{and}|e_2(I)|\le q(|e_1(I)|).$$

Thus, neither encoding can be exponentially more compact than the other.

Significance

Polynomially related encodings preserve polynomial-time solvability. If an algorithm runs in polynomial time under one encoding, and the other encoding can be translated with only polynomial overhead, then the algorithm also runs in polynomial time under the other encoding.

This is why complexity theory is usually insensitive to ordinary changes of notation, such as binary versus decimal representation of integers. Their lengths differ only by a constant factor.

Non-example

Binary encoding and unary encoding of integers are not polynomially related.

For an integer $W$,

$$|\mathrm{bin}(W)|=\Theta (\log W)\text{but}|\mathrm{unary}(W)|=\Theta (W).$$

Since $W$ is exponential in $\log W$, unary length is not bounded by any polynomial in binary length.

This difference is the source of pseudo-polynomial time: an algorithm polynomial in $W$ may be polynomial under unary encoding but exponential under binary encoding.