Polynomially related encodings

Question

CLRS states that:

For some set $I$ of problem instances, we say that two encodings $e_1$ and $e_2$ are polynomially related if there exist two polynomial-time computable functions $f_{12}$ and $f_{21}$ such that for any $i \in I$, we have $f_{12}(e_1(i)) = e_2(i)$ and $f_{21}(e_2(i)) = e_1(i)$.

My understanding of the above statement says that, for example, if we have base 2 encoding of a problem, we can convert it to base 3 encoding of the problem in polynomial time and vice versa.

I wanted to confirm from the respected community if my understanding is correct, or am I having a flaw in my understanding?

Also, If I am correct, CLRS states one more thing: "unary encodings are expensive". I want to know, what do the authors mean by that? Do they mean to say that representing 8 by 11111111 is costlier than representing 8 by 1000?

Answer 1

Yes, it's correct that you can convert between base-2 and base-3 representation (in either direction) in polynomial time. Thus, that would be a good example of two encodings that are polynomially related.

You can't convert from binary (base-2) to unary representation in polynomial time; it causes an exponential increase in the size of the instance. That's probably what is meant by "expensive".