Topological arguments for Kolmogorov complexity
Alexander Shen
alexander.shen@lirmm.fr
Andrei Romashchenko
andrei.romashchenko@lirmm.fr
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.
Introduction
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 [1]).
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(xy) ≈ 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(xy) = n/2 + O(log n). However, if we want C(xy) 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(xy) ≈ 0) and delete bits (say, at the end) one by one until we get y = Λ (the empty string) when C(xy) ≈ n). When the last bit of y is deleted, the conditional complexity C(xy) 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.
Ξ welcome to cryptostorm's member forums ~ you don't have to be a cryptostorm member to post here Ξ
Ξ any OpenVPN configs found on the forum are likely outdated. For the latest, visit here or GitHub Ξ
Ξ If you're looking for tutorials/guides, check out the new https://cryptostorm.is/#section6 Ξ
Ξ any OpenVPN configs found on the forum are likely outdated. For the latest, visit here or GitHub Ξ
Ξ If you're looking for tutorials/guides, check out the new https://cryptostorm.is/#section6 Ξ
Topological arguments for Kolmogorov complexity (pdf)

Topic Author  Posts: 611
 Joined: Sun Dec 16, 2012 6:34 am
 Contact:
Topological arguments for Kolmogorov complexity (pdf)
...just a scatterbrained network topologist & crypto systems architect……… ҉҉҉
[list] [/list]
☯ pj@ðëëþ.be ☯ keybase pgp ☯ mit pgp ☯ ðørkßötonconsole ☯ git 'er github
bitmessage: BMNBBqTcefbdgjCyQpAKFGKw9udBZzDr7f[/color]
[list] [/list]
☯ pj@ðëëþ.be ☯ keybase pgp ☯ mit pgp ☯ ðørkßötonconsole ☯ git 'er github
bitmessage: BMNBBqTcefbdgjCyQpAKFGKw9udBZzDr7f[/color]