I read that a reasonable encoding of inputs is one where the length of the encoding is no more than a polynomial of the 'natural representation' of the input. For instance, binary encodings are reasonable, but unary encodings are not.

But say that the input is a graph, and its natural representation is a vertex and edge list. Suppose that the graph has $k$ vertices. If I use unary to encode, the overall length of the input referring to the vertex list would be $O(k^2)$, i.e. $=|1^1|+|1^2|+|1^3|+...+|1^k|$. Isn't this unary encoding still a polynomial with respect to the number of vertices of the graph (which is $k$)?

What am I missing here?

  • $\begingroup$ What do you think? Why do you think it isn't? Why do you think you are missing something? $\endgroup$ – D.W. Apr 13 '20 at 16:43
  • $\begingroup$ @D.W., I think that 'at most a polynomial' of the length $N$ of the natural representation of the input should be something like within 'a logarithmic factor' of the length $N$ of the natural representation of the input, i.e. $\log_k(N)$, with $k \geq 2$ $\endgroup$ – Link L Apr 14 '20 at 1:20

Unary encoding for values 0 <= k <= N takes O(N) space. Unary encoding of an n-bit number takes $\Theta(2^n)$ space. See the difference?

  • $\begingroup$ does this mean that 'reasonable' encodings should at least be binary ? (i.e. n-bit numbers for n >= 2) ... in that case reasonable should be a logarithmic factor of N and not at most polynomial to N, unlike what I read $\endgroup$ – Link L Apr 14 '20 at 1:19
  • 1
    $\begingroup$ No, it means that using unary representation for not very large numbers isn’t exactly clever, but it also isn’t totally unreasonable. For arbitrary large integers, it is an unreasonable encoding. $\endgroup$ – gnasher729 Apr 14 '20 at 16:18

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.