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!

  • 1
    $\begingroup$ Encodings are definitely a slippery issue, but I'm confused by some of your statements. $\log(m+n)$ bits is more than a fixed number of bits once $m$ or $n$ is large enough, so doesn't that make an encoding less "powerful"? Also: A fixed number of bits never suffices for encoding an index of an object in a problem that has no upper bound on the input size $n$. Also: A bad encoding (e.g. unary) makes an algorithm seem artificially good, since we measure its speed/space usage w.r.t. the size of its encoded input. Some hard problems become "poly-time solvable" when inputs are in unary. $\endgroup$ Mar 26 '20 at 23:34
  • $\begingroup$ @j_random_hacker Sorry for the confusion. I only meant a fixed number of bits with respect to a single input "object." So in my example, an object would be a single edge or a single vertex. And so, for example, if it takes 1 bit to encode a vertex and 3 for an edge, encoding a graph consisting of 4 vertices and 2 edges would take 10 bits, and DFS would run in polynomial time in the number of bits in this case. $\endgroup$
    – kanso37
    Mar 27 '20 at 0:04
  • $\begingroup$ But what I meant with the $\log (m + n)$ example was maybe there is a clever to encode a graph (after all, that is all we want as input) such that the entire graph (vertices and edges and all) can be encoded in $\log (m + n)$ bits. Doing so might be super complicated and require a ton of cases, but I don't see why it can't be done in theory. And since the algorithm on such an input would still run in time $O(m + n)$, the runtime in the number of bits would be exponential due to the new encoding. $\endgroup$
    – kanso37
    Mar 27 '20 at 0:06
  • $\begingroup$ (The new encoding would be more powerful because it conveys more information in less bits since you aren't saying anymore, "You always need $k$ bits per object.") $\endgroup$
    – kanso37
    Mar 27 '20 at 0:08
  • $\begingroup$ With 3 bits to encode an edge, you can only encode 8 possible edges. If you have a graph with thousands of vertices and millions of edges, how do you represent each of those edges in 3 bits? You can't -- an edge (in a vertex-labelled graph, at least) needs to identify its 2 endpoints, and 3 bits (or any constant number of bits) is not enough to do this for an arbitrarily large graph. You need at least $O(\log n)$ bits per edge. $\endgroup$ Mar 27 '20 at 11:32

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.

  • $\begingroup$ Thanks for the detailed answer! The link is also much appreciated. I hadn't heard of ideas like "information-theoretic lower bounds" before. $\endgroup$
    – kanso37
    Mar 27 '20 at 17:50

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.