Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Have you tried asking this on Cryptography SE ? – Zsbán Ambrus Jun 27 '14 at 15:50
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. Jun 27 '14 at 18:51
up vote 9 down vote accepted

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:

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

share|cite|improve this answer
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 Jun 27 '14 at 17:07
@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 Jun 27 '14 at 23:26

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

share|cite|improve this answer
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 Jun 27 '14 at 21:32
I feel the seed contains more information than the generated psuedo-random string as we can compute the generated string from the seed. – Kaveh Jun 28 '14 at 0:02
@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. Jun 28 '14 at 0:06

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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