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?


1 Answer 1


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.

  • $\begingroup$ Nice! Does that mean that the encoded strings can be of any length as far as the length difference is polynomial? (their lengths could be described by exponential functions for example, but they are still polynomially related). $\endgroup$
    – mrk
    Sep 10, 2012 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.