Advanced Algorithms
(a) Explain what is meant by the Kolmogorov Complexity K(n) of a natural
number n. [5 marks]
(b) Consider a graph of the function K(n) plotted against n:
(i) Show that it is smooth, in the sense that for any n and fairly small value
of k the value of K(n + k) will be quite close to the value of K(n).
[3 marks]
(ii) Show that it is rough, in the sense that for any N there are two values of
n1 and n2 between N and 2N such that K(n1) is about 2K(n2)
, i.e. one
has a complexity exponentially bigger than the other. [3 marks]
(iii) Explain why the graph is bounded above by some straight line of the form
n + c and comment on what the constant represents. [3 marks]
(iv) Explain why for any constant k there will be a value N such that n > N
implies that K(n) > k. [3 marks]
(v) Demonstrate that there is no constant N such that n > N implies
K(n) > log log log log n. [3 marks]