We present several applications of simple topological arguments (such as non-contractibility of a sphere and similar results) to Kolmogorov complexity. It turns out that discrete versions of these results can be used to prove the existence of strings with prescribed complexity with O(1)-precision (instead of usual O(logn)-precision). In particular, we improve an earlier result of M. Vyugin and show that for every n and for every string x of complexity at least n + O(logn) there exists a string y such that both C(x∣y) and C(y∣x) are equal to n + O(1). We also show that for a given tuple of strings xi (assuming they are almost independent) there exists another string y such that the condition y makes the complexities of all xi twice smaller with O(1)-precision. The extended abstract of this paper was published in [6].
