# Help in understanding 'reasonable' encoding of inputs

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?

• What do you think? Why do you think it isn't? Why do you think you are missing something? – D.W. Apr 13 '20 at 16:43
• @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$ – Link L Apr 14 '20 at 1:20

## 1 Answer

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?

• 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 – Link L Apr 14 '20 at 1:19
• 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. – gnasher729 Apr 14 '20 at 16:18