2
$\begingroup$

Is there an equation that relates minimum time complexity, minimum space complexity, and entropy of the output of a function? It seems to me that there should be a relatively intuitive relationship between the three, something like $E=f(T+S)$ where $E$ is shannon entropy of the output, $T$ is time, $S$ is space, and f is a linear function or something like that. The main argument being that any function can be written as a hash map that takes its input to its output. This hashmap could be compressed based on its entropy.

I have a hunch that the only way to decrease the space an algorithm uses more than that is to increase the time complexity, as if the hashmap is moved onto a time axis instead of a space one. Is this crazy? Has there been any research done on this subject?

Edit for clarification: What I mean by "entropy of the output of a function" is this. Assume a function $g$ takes as input a bit string $x$ and outputs a message $y$. Now $g$ can thought of a source who's $x$th output is $y$. By "entropy of the output" I mean the shannon entropy of $g$ when thought of as a source.

Again, the argument is that $g$ can be implemented using a hash map in exponential space but in $O(1)$ time. However, I have a hunch that it seems reasonable that this space complexity can be reduced based on the entropy of $g$ (i.e. the entropy of the hashmap) and still maintain $O(1)$ time, essentially by compressing the hash map.

Beyond this reduction I also have a hunch that that you can decrease the space further, but in doing so you have to increase time proportionally. The idea being that you can't actually compress the information in the hash map any more than you already have (even when you compress using other measures of entropy like kolmogorov complexity), you can just "move" it along the time axis.

$\endgroup$
  • $\begingroup$ What do you mean by entropy of the output of a function? $\endgroup$ – Martin Berger Feb 9 at 10:27
  • $\begingroup$ @MartinBerger Edited for clarification $\endgroup$ – William Oliver Feb 9 at 14:22
  • 1
    $\begingroup$ Shannon entropy requires a random source. Where's the randomness in your setup? $\endgroup$ – Aryeh Feb 9 at 19:21
  • $\begingroup$ @Aryeh Assume that when we think of $g$ as a source it actually is a random source. The probability of each symbol being given by the limit of the sample probability of each symbol as the length of the input goes to infinity. For the sake of this question, you can assume each event is independent. $\endgroup$ – William Oliver Feb 9 at 20:05
1
$\begingroup$

(Too long for a comment.)

There are two aspects to your question. There is the idea of a time-"space" tradeoff, and the idea of entropy as a measure or bound for how hard this tradeoff must be for a problem. Both aspects have some issues relating to how theorists usually study these problems. Here is why and some suggestions.

Regarding entropy: This is an interesting idea but either wrong or hard to formalize for several reasons. Notice that a program that just spits out a long sequence of independent bits (whether it produces them or reads them from an input) has very high entropy but is also very simple. Its running time and space requirements are minimal. And in general there are deterministic algorithms with 0 entropy that solve very difficult problems on both time and space axis. Finally, many problems of theoretical interest are decision problems where the output is just one bit.

So entropy seems unrelated at least from usual perspectives, and you have to think it through more or else switch to a notion like Kolmogorov complexity (e.g. compressibility of the truth-table of a decision problem or something).

Regarding time-space tradeoffs: It's hard to reconcile your ideas with what we traditionally call space-time tradeoffs, which refer to time and memory usage of an algorithm starting from scratch (unlike your hashtables etc). It is studied but very, very hard. You are asking to go even farther and relate this tradeoff to some other notion of complexity of the problem, so we are probably even farther from those results (maybe not in some specific domain?).

However, I do think your intuition can be captured by complexity classes involving "advice". For instance, P/poly are problems solved by polynomial time algorithms with access to polynomial-length advice strings. You seem to be observing that all problems are in O(n)/EXP: trivial linear-time algorithm, or constant time in word RAM model, that has access to a lookup table for all answers. Whereas the problem might not be in P/poly or might not be in Exp/O(1) or so on. We trade off advice space for running time. I don't know of work on this -- I'm not an expert so maybe it exists, but it sounds hard. A general theorem relating this tradeoff to a measure of complexity of the problem would be very cool, but even harder.

$\endgroup$
  • $\begingroup$ I think this answers my question about whether there is existing research on the subject, but the criticisms you've come up with have crossed my mind. The key thing is that the "a program that just spits out a long sequence of independent bits" only has high entropy if the input has high entropy, so the entropy is actually the entropy of the input, not the entropy of the output. An encryption algorithm, for example, is pretty useless unless the method of key generation has high entropy. $\endgroup$ – William Oliver Feb 10 at 20:57
  • $\begingroup$ Furthermore, a decision problem outputs just one bit for one input, yes, but this doesn't mean that the hashtable mentioned doesn't have high entropy. This will be as many bits (computer bits, not bits as in shannon bits) as there are possible inputs. $\endgroup$ – William Oliver Feb 10 at 20:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.