Random noise and Kolmogorov complexity
Alexander Shen  1  
1 : Laboratoire dÍnformatique de Robotique et de Microélectronique de Montpellier
Université de Montpellier : UMR5506, Centre National de la Recherche Scientifique : UMR5506

Take a string of length n and complexity, say, 0.5n. Change each bit with probability 0.1. Then with high probability the resulting string will have complexity at least 0.51n. To prove this (and to get an exact bound), we use some tools from information and probability theory. (Based on the work of Peter Gacs, Gleb Posobin and myself)

Personnes connectées : 1