<p>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.</p>

<p>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)$.</p>

CC BY-SA 3.0
2014-06-27T21:32:24.697Z
I understand, I just wonder how much can be salvaged or patched. In that case, you could add the constraint that f is polynomially invertible, but that feels ad-hoc
Arthur B
CC BY-SA 3.0
2014-06-28T00:02:44.910Z
I feel the seed contains more information than the generated psuedo-random string as we can compute the generated string from the seed.
Kaveh
CC BY-SA 3.0
2014-06-28T00:06:52.590Z
@Kaveh, if you are talking in an information-theoretic sense: if the pseudorandom generator is invertible (maybe not in polynomial time, but in principle), then its input and output have the same amount of information, information-theoretically; otherwise, if the pseudorandom subjective is non-invertible, then you are right.
D.W.
CC BY-SA 3.0
2014-06-27T19:01:39.913Z
2014-06-27T19:01:39.913Z
D.W.
<p>I'm not aware of an information-theroetic computational model, <em>but</em> there are clear applications of information theory to computational complexity.</p>

<p>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.</p>

<p>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}.</p>

<hr>

<p>{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.</p>

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

CC BY-SA 3.0
2014-06-27T17:46:44.527Z
2014-06-27T19:38:16.937Z
2014-06-27T19:38:16.937Z
Ari Trachtenberg
<p>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. </p>

<p>However, in this time-bounded setting, not all of the usual <em>theorems</em> 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 <a href="http://www.research.rutgers.edu/~troyjlee/thesis.pdf">Troy Lee's thesis</a>.</p>

<p>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:</p>

<ul>
<li><p>Grunwald and Vitanyi. <a href="http://arxiv.org/abs/cs/0410002">Shannon Information and Kolmogorov Complexity</a></p></li>
<li><p>Hammer, Romashchenko, Shen, Vereshchagin. <a href="http://dx.doi.org/10.1006/jcss.1999.1677">Inequalities for Shannon Entropy and Kolmogorov Complexity</a>.</p></li>
</ul>

<p>(On the other hand, there are some properties that are known not to be shared between the two, see Muchnik &amp; Vereshchagin, <a href="http://dx.doi.org/10.1007/11753728_29">Shannon Entropy vs. Kolmogorov Complexity</a>.)</p>

CC BY-SA 3.0
2014-06-27T17:07:30.927Z
My main concern would be that the time is Turing Machine dependent. Since Turing machines can emulate each other with at most a polynomial speed-up or speed-down, penalizing the complexity by log(log(t)) would seem to make them equivalent up to an additive constant. However, Levin complexity uses log(t), I'm not sure why.
Arthur B
CC BY-SA 3.0
2014-06-27T23:26:37.570Z
@Arthur B: I understand your concern, but there are probably several standard ways around it. Typically when you prove a statement about, e.g., time-bounded Kolmogorov complexity, you might prove a statement of the form "for all polynomial time bounds $t(n)$, ...", at which point any polynomial slow-down/speed-up incurred by changing universal machine is no longer relevant, since the statement applies in any case. (I didn't follow what you were saying about $\log \log t$, but I think that's just a different way to try to handle this problem...)
Joshua Grochow
CC BY-SA 3.0
2014-06-27T16:25:34.993Z
2014-06-27T16:25:34.993Z
Joshua Grochow
<p>I apologize, this is a bit of a "soft" question.</p>

<p>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.</p>

<p>Is there a way to formalize the concept of "polynomially knowable"?</p>

<p>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.</p>

<p>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.</p>

<p>Has such a generalization been studied? Can it be made consistent?</p>

CC BY-SA 3.0
2014-06-27T15:50:36.250Z
Have you tried asking this on Cryptography SE https://crypto.stackexchange.com/ ?
Zsbán Ambrus
CC BY-SA 3.0
2014-06-27T18:51:08.943Z
It's possible that the crypto folks might have an answer, but the question is perfectly on-topic here, and I suspect it might have a better chance of getting a good answer here.  Just a quick note: please don't re-post the same question on Crypto.SE; cross-posting on multiple SE sites is prohibited by site rules.
D.W.
<cc.complexity-theory><it.information-theory><polynomial-time>
Is there a generalization of information theory to polynomially knowable information?
Arthur B
# Is there a generalization of information theory to polynomially knowable information?

(Asked by: username_0 on 2014-06-27)

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?

**Tags:** cc.complexity-theory, it.information-theory, polynomial-time

> **Comments:**
> **username_1**: Have you tried asking this on Cryptography SE https://crypto.stackexchange.com/ ?  
> **username_2**: It's possible that the crypto folks might have an answer, but the question is perfectly on-topic here, and I suspect it might have a better chance of getting a good answer here.  Just a quick note: please don't re-post the same question on Crypto.SE; cross-posting on multiple SE sites is prohibited by site rules.  

---

## 3 answers

### Answer by username_5 on 2014-06-27. Score: 9 | Accepted answer

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](http://www.research.rutgers.edu/~troyjlee/thesis.pdf).

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](http://arxiv.org/abs/cs/0410002)
* Hammer, Romashchenko, Shen, Vereshchagin. [Inequalities for Shannon Entropy and Kolmogorov Complexity](http://dx.doi.org/10.1006/jcss.1999.1677).

(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](http://dx.doi.org/10.1007/11753728_29).)

> **Comments:**
> **username_0**: My main concern would be that the time is Turing Machine dependent. Since Turing machines can emulate each other with at most a polynomial speed-up or speed-down, penalizing the complexity by log(log(t)) would seem to make them equivalent up to an additive constant. However, Levin complexity uses log(t), I'm not sure why.  
> **username_5**: @username_0: I understand your concern, but there are probably several standard ways around it. Typically when you prove a statement about, e.g., time-bounded Kolmogorov complexity, you might prove a statement of the form "for all polynomial time bounds $t(n)$, ...", at which point any polynomial slow-down/speed-up incurred by changing universal machine is no longer relevant, since the statement applies in any case. (I didn't follow what you were saying about $\log \log t$, but I think that's just a different way to try to handle this problem...)  

---

### Answer by username_2 on 2014-06-27. Score: 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)$.

> **Comments:**
> **username_0**: I understand, I just wonder how much can be salvaged or patched. In that case, you could add the constraint that f is polynomially invertible, but that feels ad-hoc  
> **username_3**: I feel the seed contains more information than the generated psuedo-random string as we can compute the generated string from the seed.  
> **username_2**: @username_3, if you are talking in an information-theoretic sense: if the pseudorandom generator is invertible (maybe not in polynomial time, but in principle), then its input and output have the same amount of information, information-theoretically; otherwise, if the pseudorandom subjective is non-invertible, then you are right.  

---

### Answer by username_4 on 2014-06-27. Score: 0

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


---

