2
$\begingroup$

CLRS states that:

For some set $I$ of problem instances, we say that two encodings $e_1$ and $e_2$ are polynomially related if there exist two polynomial-time computable functions $f_{12}$ and $f_{21}$ such that for any $i \in I$, we have $f_{12}(e_1(i)) = e_2(i)$ and $f_{21}(e_2(i)) = e_1(i)$.

My understanding of the above statement says that, for example, if we have base 2 encoding of a problem, we can convert it to base 3 encoding of the problem in polynomial time and vice versa.

I wanted to confirm from the respected community if my understanding is correct, or am I having a flaw in my understanding?

Also, If I am correct, CLRS states one more thing: "unary encodings are expensive". I want to know, what do the authors mean by that? Do they mean to say that representing 8 by 11111111 is costlier than representing 8 by 1000?

$\endgroup$

1 Answer 1

3
$\begingroup$

Yes, it's correct that you can convert between base-2 and base-3 representation (in either direction) in polynomial time. Thus, that would be a good example of two encodings that are polynomially related.

You can't convert from binary (base-2) to unary representation in polynomial time; it causes an exponential increase in the size of the instance. That's probably what is meant by "expensive".

$\endgroup$
1
  • $\begingroup$ Thankyou, It helped a lot! $\endgroup$ Apr 24, 2020 at 18:03

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.