<p>take e.g. all possible bitstrings of length n=10,000. there are 2^10,000 of them. imagine that for each of those strings we knew the length of the shortest program that could produce the string. what would the distribution of the lengths of those programs look like?</p>

CC BY-SA 3.0
2017-09-24T09:40:24.860Z
How precise of an answer do you want? By a counting argument, only a $2^{-c}$ fraction of strings can possibly have a KC of less than $2^{10000-c}$, or in other words, all but $o(n)$ strings have complexity $n-o(n)$.
usul
CC BY-SA 3.0
2017-09-29T19:29:49.267Z
PS. That should say all but $2^{o(n)}$ strings have complexity $n - o(n)$, or equivalently all but an $o(1)$ fraction of strings.
usul
CC BY-SA 3.0
2017-09-30T20:28:52.397Z
Thank you, that is interesting. I suppose I'm interested in as precise an answer as is currently possible, but would take anything more than I know right now which is near zero :) The counting argument is probably obvious to most, but I would be interested in hearing it described.
RoboTeddy
<cc.complexity-theory><kolmogorov-complexity>
What's the distribution of the Kolmogorov complexity of the elements in the set of bitstrings of length n?
RoboTeddy
# What's the distribution of the Kolmogorov complexity of the elements in the set of bitstrings of length n?

(Asked by: username_0 on 2017-09-24)

take e.g. all possible bitstrings of length n=10,000. there are 2^10,000 of them. imagine that for each of those strings we knew the length of the shortest program that could produce the string. what would the distribution of the lengths of those programs look like?

**Tags:** cc.complexity-theory, kolmogorov-complexity

> **Comments:**
> **username_1**: How precise of an answer do you want? By a counting argument, only a $2^{-c}$ fraction of strings can possibly have a KC of less than $2^{10000-c}$, or in other words, all but $o(n)$ strings have complexity $n-o(n)$.  
> **username_1**: PS. That should say all but $2^{o(n)}$ strings have complexity $n - o(n)$, or equivalently all but an $o(1)$ fraction of strings.  
> **username_0**: Thank you, that is interesting. I suppose I'm interested in as precise an answer as is currently possible, but would take anything more than I know right now which is near zero :) The counting argument is probably obvious to most, but I would be interested in hearing it described.  

---

## 0 answers

