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.