# An equation relating Time complexity, Space complexity, and entropy of output

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.

• What do you mean by entropy of the output of a function? Feb 9 '19 at 10:27
• @MartinBerger Edited for clarification Feb 9 '19 at 14:22
• Shannon entropy requires a random source. Where's the randomness in your setup? Feb 9 '19 at 19:21
• @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. Feb 9 '19 at 20:05

(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?).