Is there a generalization of information theory to polynomially knowable information?

Question

I apologize, this is a bit of a "soft" question.

Information theory has no concept of computational complexity. For example, an instance of SAT, or an instance of SAT plus a bit indicating satisfiability carry the same amount of information.

Is there a way to formalize the concept of "polynomially knowable"?

Such a framework could define for example the notion of polynomial-KL divergence between a random variable X relative Y as the number of bits needed to compute X in polynomial time given Y.

Likewise, the entropy of a random variable X could be defined as the number of bits needed to encode X in a way that can be decoded in polynomial time.

Has such a generalization been studied? Can it be made consistent?

Answer 1

Yes. Time-bounded Kolmogorov complexity is at least one such "generalization" (though strictly speaking it's not a generalization, but a related concept). Fix a universal Turing machine $U$. The $t(n)$-time-bounded Kolmogorov complexity of a string $x$ given a string $y$ (relative to $U$), denoted $K^t_U(x | y)$ (the subscript $U$ is often supressed) is defined as the shortest string $p$ (a "program" for $U$) such that $U(p,y)=x$ and such that the computation of $U(p,y)$ takes at most $t(|x|)$ time. If you take this as your definition of "conditional information", then you can likewise define all the usual concepts from information theory.

However, in this time-bounded setting, not all of the usual theorems of information theory are known to hold. For example, symmetry of information is known to hold for usual Kolmogorov complexity (no time bound), but not known to hold for time-bounded. See, for example, Chapter 6 of Troy Lee's thesis.

If you are concerned that this applies to strings rather than distributions, I suggest reading the following papers, which say that in fact Kolmogorov complexity of strings and Shannon entropy of distributions are very closely related:

• Grunwald and Vitanyi. Shannon Information and Kolmogorov Complexity

• Hammer, Romashchenko, Shen, Vereshchagin. Inequalities for Shannon Entropy and Kolmogorov Complexity.

(On the other hand, there are some properties that are known not to be shared between the two, see Muchnik & Vereshchagin, Shannon Entropy vs. Kolmogorov Complexity.)

Answer 2

One issue is that many of the theorems we're used to in information theory, don't hold in the computational world. Therefore, even if we formalized a computational analog of entropy, the resulting theory might not look like information theory any more.

For instance, if $f$ is a deterministic function, then $H(f(X)) \le H(X)$. However, for any plausible computational notion of entropy, this will no longer hold: think of a pseudorandom generator, for instance, which stretches a short seed into a long pseudorandom output. By any conceivable definition of computational entropy I can imagine, that long pseudorandom output will have large computational entropy (it is computationally indistinguishable from a uniform distribution on those long strings), thus violating $H(f(X)) \le H(X)$.

Answer 3

I'm not aware of an information-theroetic computational model, but there are clear applications of information theory to computational complexity.

For example, the classic $n \log n$ lower bound on comparison-based sorting is based on an information-theoretic argument about the height of a decision tree needed to distinguish between all possible orders of inputs. You can similarly make trivial information-theoretic bounds on the computational complexity of search, order-statistics, average, etc.

More typically, information-theoretic results can serve as lower bounds on computational complexity. For example, Yao's "information-theoretic" result on communication complexity {1} implies computational lower bounds on determining whether two sets are equal. More sophisticated applications of communication complexity provide time-space tradeoffs for Turing machines {2}.

---

{1} Yao, Andrew Chi-Chih. "Some complexity questions related to distributive computing (preliminary report)." Proceedings of the eleventh annual ACM symposium on Theory of computing. ACM, 1979.

{2} Eyal Kushilevitz: Communication Complexity. Advances in Computers 44: 331-360 (1997).