3
$\begingroup$

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$?

|cite|improve this question
$\endgroup$
  • 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$ – Artem Kaznatcheev♦ Jun 11 '12 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$ – Suresh Venkat Jun 11 '12 at 15:16
10
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ Just to add, this is an example of the general phenomenon that most objects are hard. $\endgroup$ – Tsuyoshi Ito Jun 12 '12 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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