Problem Detail: 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 $Iin 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?
Asked By : saadtaame
Answered By : Nicholas Mancuso
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/3462 Ask a Question Download Related Notes/Documents
