0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you (instead of just citing a chapter) describe what is making you confused? $\endgroup$ – Pål GD Nov 27 '18 at 16:38
  • $\begingroup$ Downvoters, please comment on what you think can improve this question. I believe that there is a useful question hiding in there somewhere, we just need to find it. Please help rewriting this question to a useful one. $\endgroup$ – Pål GD Nov 27 '18 at 16:39
0
$\begingroup$

Everything is in binary in your electronic computer. However:

  1. We don't want to have to throw away all of the theory of computation if somebody builds a really fast ternary computer.

  2. 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.

$\endgroup$
  • $\begingroup$ Thank you very much. It finally makes a lot more sense than before! $\endgroup$ – Anurag Shah Nov 27 '18 at 16:49

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.