I'm reading through Computers and Intractability: A guide to the Theory of NP-Completeness by Michael R. Garey and David S. Johnson, p. 20 and I came across this concept of a function that is polynomially related to input lengths obtained using some encoding scheme. Let $$Len:D_{\Pi}\rightarrow \mathbb Z^+$$ be a function that maps instances $\in D_{\Pi}$ (the set of instances of decision problem $\Pi$) to positive integers (lengths). Let $x$ be the string obtained from $I\in D_{\Pi}$ under some encoding $e$. If there exist polynomials $p$ and $p'$ such that $$Len(I) \le p(|x|)$$ and $$|x| \le p'(Len(I)),$$ We say that $Len$ is polynomially related to the input lengths obtained by the encoding $e$. I cannot digest that; my understanding is that two encodings are polynomially related if converting from one another requires a polynomial amount of time. Can anybody clarify things a bit?
Polynomially related lengths under two different encodings
complexity theory;polynomial time;encoding scheme
Garey and Johnson are referring to the fact that any encoding scheme for some instance $I$ of a problem $\Pi$ will only differ in length (i.e. number of bits) by a polynomial amount. For example, consider two possible ways to encode a graph: adjacency matrix, and adjacency list.It is not possible to obtain a super-polynomial speedup by using one encoding over another for various instances of problems. Again, this notion relies on the fact that encodings are reasonable. That is to say, we are not unnecessarily padding our encoding with some junk information.