Hi I have been reading Ch 34(NP-Completeness) Section 34.1 of CLRS and I am confused why do we need to consider different encodings. Everything is represented as binary at the end so why consider different encodings of the input? Any help is highly appreciated.
Everything is in binary in your electronic computer. However:
We don't want to have to throw away all of the theory of computation if somebody builds a really fast ternary computer.
More importantly, the stuff we wish to compute upon isn't binary. It's strings and graphs and numbers and things like that. So the very first thing you need to do is to encode your string/graph/number into a form that fits into your model of computation. And, since we are forced to encode, we'd better consider whether our encoding is a good one.
We have to use an encoding to map the instance of the problem into binary (or whatever the computer uses as its alphabet), and often it doesn’t matter what encoding you use. For example, we don’t want to worry about binary versus ternary.
More precisely, we don’t want to worry about the difference between any two encoding schemes which are polynomially equivalent. What do I mean by this? Suppose we have a problem $P$, where an instance $I$ of $P$ can be encoded (in binary, say) as either $f_1(I)$, with length $n_1(I)$, or $f_2(I)$, with length $n_2(I)$. We say that $f_1$ and $f_2$ are polynomially equivalent when there are polynomials $p_1$, $p_2$ such that, for all instances $I$, $n_1(I)\leq p_1(n_2(I))$ and $n_2(I)\leq p_2(n_1(I))$.
This is often so obvious that we forget the distinction. For example, no programmer seriously considers representing an integer $n$ as a string of length $n$ when any kind of speed is required. But what about sparse polynomials and dense polynomials, for example? To expand on that example, a SAT problem can be considered as a big polynomial, and we’re asking if it has a root over $GF(2)$. But it’s critical that we give that polynomial in some kind of sparse representation. The dense form of the polynomial lists the $2^k$ terms, where the SAT problem has $k$ variables. In that representation, we have to input $2^k$ bits to the machine. If we have to do that, then we can solve this problem, let’s call it DENSE-SAT, in polynomial time, just by exhaustion. We can’t solve the problem any faster, of course, but the huge input changes the meaning of polynomial time so that our previously terrible algorithm looks good in comparison to the input length.
So in general we have to be slightly careful to specify the input format. Not very careful, because it doesn’t matter up to polynomial equivalence, but careful enough.