1
$\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$
2
  • $\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
1
$\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$
1
  • $\begingroup$ Thank you very much. It finally makes a lot more sense than before! $\endgroup$ – Anurag Shah Nov 27 '18 at 16:49
1
$\begingroup$

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.

$\endgroup$

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.