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

CC BY-SA 3.0
2012-06-12T01:44:28.813Z
Just to add, this is an example of the general phenomenon that most objects are hard.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-11T10:32:22.160Z
2012-06-11T10:43:19.307Z
2012-06-11T10:43:19.307Z
Marzio De Biasi
<p>In connection to this question:
<a href="https://cstheory.stackexchange.com/questions/7993/expected-values-of-kolmogorov-complexity-in-a-random-sample">Expected values of Kolmogorov complexity in a random sample</a></p>

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

CC BY-SA 3.0
2012-06-11T12:28:53.227Z
I think this is off-topic for cstheory as not _research-level_. However, you can flag it for migration to [CS.SE](http://cs.stackexchange.com/).
Artem Kaznatcheev
CC BY-SA 3.0
2012-06-11T15:16:53.283Z
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 :)
Suresh Venkat
<cc.complexity-theory><computability><kolmogorov-complexity>
More complex integers
v s
# More complex integers

(Asked by: username_0 on 2012-06-11)

In connection to this question:
[Expected values of Kolmogorov complexity in a random sample](https://cstheory.stackexchange.com/questions/7993/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$?

**Tags:** cc.complexity-theory, computability, kolmogorov-complexity
> **Comments:**
> **username_1**: I think this is off-topic for cstheory as not _research-level_. However, you can flag it for migration to [CS.SE](http://cs.stackexchange.com/).  
> **username_2**: 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 :)  

---

## 1 answers

### Answer by username_3 on 2012-06-11. Score: 10 | Accepted answer

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

> **Comments:**
> **username_4**: Just to add, this is an example of the general phenomenon that most objects are hard.  

---

