In connection to this question: Expected values of Kolmogorov complexity in a random sample

Let $n$ be number of bits. Let $A = \{0,1,2,\dots,2^{n}-1\}$ be indexed by the $n$-bits. Let $ \delta > 0$ be fixed. Is there an estimate of what fraction of integers in $A$ can have Kolmogorov complexity be greater than $\delta n$?

  • 2
    $\begingroup$ I think this is off-topic for cstheory as not research-level. However, you can flag it for migration to CS.SE. $\endgroup$ Commented Jun 11, 2012 at 12:28
  • 5
    $\begingroup$ It may not be research-level to some, but I didn't know the answer, and could have imagined asking it. It might fall under the category of "easy question in subarea X not known to researchers in subarea Y" --- or I'm just illiterate :) $\endgroup$ Commented Jun 11, 2012 at 15:16

1 Answer 1


The argument is the same, there are only $1 + 2 + 4 + ... + 2^{\delta n - 1}$ programs shorter than $\delta n$ so there are at least $2^n - (2^{\delta n} - 1)$ integers with $K(x) \geq \delta n$.

  • 3
    $\begingroup$ Just to add, this is an example of the general phenomenon that most objects are hard. $\endgroup$ Commented Jun 12, 2012 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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