0

if I have a natural number $a(n,m)$ that depends on some $n$ and $m$, where $m$ is fixed,

isn't then the Kolmogorov complexity of it simply its logarithm?

Rhjg
  • 2,029
  • Why would it be? – anomaly Jul 29 '15 at 18:43
  • Since one needs ln(a(n,m)) bits to code it? – Rhjg Jul 29 '15 at 18:44
  • I can write the function $a(n) = 2^n$ in $O(1)$ bits (for a given language). – anomaly Jul 29 '15 at 18:48
  • But if I have a natural number $k$, then the Kolmogorov complexits is $\log(k)$ isn't it? – Rhjg Jul 29 '15 at 18:51
  • Again, why? Kolmogorov complexity is usually presented in the context of representing a family of objects via some language. If I consider $2^n$ as a bit string, I can write a program with size $O(1)$ that inputs $n$ and outputs $2^n = 10\cdots 0_2$. – anomaly Jul 29 '15 at 19:02

1 Answers1

3

The Kolmogorov complexity of a number is the length of the shortest program that prints out that number. If your number has $n$ digits, then there is a program of length approximately $n$ which prints out that number by printing all of its digits, but sometimes there are much shorter programs.

For example, a for loop going from $1$ to $k$ can print out the number $2^k$, so the Kolmogorov complexity of $n = 2^k$ is at most approximately $\log k$, or $\log \log n$. (I'm ignoring constants throughout this discussion.)

Qiaochu Yuan
  • 419,620
  • Why is it at most log k? – Rhjg Aug 01 '15 at 14:41
  • @Rhjg: are you asking about the "at most" part or about the "$\log k$" part? The "at most" part is because, if $k$ itself admits a short description, you can do even better (for example, if $k$ is itself a power of $2$). The "$\log k$" part is because that's how long it takes to just write out all the digits of $k$. – Qiaochu Yuan Aug 01 '15 at 16:22
  • If I count configurations on $[-m,m]\times [0,n-1]\subset \mathbb{Z}^2$ due to some dynamics...and when I call the number of all possible configurations on it for example $c(n,m)$, why is then the kolmogorov complexity $\ln c(n,m)$? – Rhjg Aug 01 '15 at 16:37
  • @Rhjg: I'm not sure what you're asking. Are you still asking about the complexity of the individual number $c(n, m)$ (rather than, say, the complexity of the function $(n, m) \mapsto c(n, m)$)? If so, again, it's at most approximately $\log c(n, m)$, but it can be less. – Qiaochu Yuan Aug 01 '15 at 16:38
  • Back to your example. If a for loop can print out 2^k, why does this then have kolmogorv complexits at most log(k). Where does the log come from at all? – Rhjg Aug 01 '15 at 16:46
  • @Rhjg: the log comes from writing out the digits of $k$ in the for loop. Again, if $k$ has a particularly simple description, you can do better than this. – Qiaochu Yuan Aug 01 '15 at 16:55
  • If I have $n=8=2^3$, then I have $8=1000_2$, that is the kolmogorov complexity is at most $4$, isn't it? How now get that it even is at most log(3)? – Rhjg Aug 01 '15 at 16:57
  • I do not understand that: No matter which natural number n is... the kolmogorov complexity is always at most log(n)? or only for some n? – Rhjg Aug 01 '15 at 17:15