Can a more powerful encoding of an input make an algorithm that is polynomial in the number of inputs become exponential?

Question

This is probably a very basic question but one that I am having trouble finding a definitive answer for since this kind of thing is skimmed over in most introductory algorithms courses. Take an algorithm like DFS that runs in time polynomial in the number of inputs. In this case your input is a graph with $n$ vertices and $m$ edges, and your algorithm runs in time $O(m + n)$.

But we know that in reality we must always consider the lengths of binary encodings when calculating runtime. This is why something like the dynamic programming algorithm for Knapsack isn't actually polynomial.

DFS takes in $n + m$ "objects" as input. If we say that each object takes a fixed number of bits (e.g., each vertex takes 1 bit to encode and each edge takes 3 bits), then it makes sense to me that the algorithm is indeed polynomial in the input. But is there any reason that we need a fixed number of bits for each object? Might there exist a more powerful encoding of the input that takes $\log (m+n)$ bits, suddenly making the algorithm exponential?

One thought I had was just that there is an assumption that any practical encoding in the real world is going to require a fixed number of bits for every extra "object" given as input, whether the objects be vertices, letters in a string, etc.; thus it is most useful to think about runtimes this way. But I want to make sure since I think this is fundamental to my understanding. Thanks in advance!

Answer 1

There are $2^{n^2}$ labelled directed graphs on $n$ vertices. Therefore, any such graph requires at least $n^2$ bits to represent it. So, there is no hope for an encoding scheme that always uses at most $O(\log n)$ bits and can encode all graphs.

If you want to focus on labelled directed graphs with $n$ vertices and $m$ edges, there are ${n^2 \choose m}$ of them, which for $m \ll n^2$ is approximately $(e n^2/m)^m / \sqrt{2\pi m}$, and thus you'll need at least $m \lg (n^2/m) + O(m)$ bits to represent all of them. Notice that this is $\Omega(m)$, so there is no hope for an encoding scheme that uses only $O(\log m)$ bits (or $O(\log(m+n))$ bits) and can represent all such graphs.

Of course, you can consider encodings that are logarithmically short, but they can only express a tiny fraction of all possible graphs. Yes, if you wanted to represent the input in that way and solve a reachability problem on such a graph, then ordinary DFS would take time exponential in the size of the input.

Related: You might be interested in succinct data structures.