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

Question

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.

Answer 1

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