Topological arguments for Kolmogorov complexity
We present several application of simple topological arguments in problems of Kolmogorov complexity. Basically we use the standard fact from topology that the disk is simply connected. It proves to be enough to construct strings with some nontrivial algorithmic properties.
In this paper we show that a very simple and intuitive topological technique can be surprisingly effective in algorithmic information theory. We present several examples of “topological” proofs of existence of strings with some nontrivial algorithmic properties. We focus on technical aspects of the arguments, assuming that the reader is familiar with basic notions of algorithmic information theory such as Kolmogorov complexity and the mutual information (see the classic textbook ).
Let us start with an example. Consider a string x that has complexity n (we consider plain complexity C(x), but this does not matter for now). We want to find a string y such that C(x|y) ≈ n/2. This can be done as follows: consider the shortest description p of x; it has length n; let y be the first half of this description. Then it is easy to check that C(x|y) = n/2 + O(log n). However, if we want C(x|y) to be close to n/2 with (maximal possible) precision O(1), one needs a different argument. Let us start with y = x (when C(x|y) ≈ 0) and delete bits (say, at the end) one by one until we get y = Λ (the empty string) when C(x|y) ≈ n). When the last bit of y is deleted, the conditional complexity C(x|y) changes by at most O(1), so it cannot cross the threshold n/2 without visiting O(1)-neighborhood of n/2. Topological arguments of this type can be used in two (and more) dimensions, though they become a bit less trivial. We provide several examples of this type in the following sections.