2012/06/30 by Alexander Shen, Andrei Romashchenko · 1 citation
Computer Science · Mathematics · #cs.CC #cs.DM #cs.IT #math.IT
paper · pdf · doi:10.4204/eptcs.90.10
Extended version
arxiv created 2015/01/26 · arxiv updated 2015/01/27
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.