Kolmogorov Complexity with Error
Lance Fortnow, Troy Lee, Nikolay Vereshchagin · 2004
Abstract. We introduce the study of Kolmogorov complexity with error. For a metric d, we define Ca(x) to be the length of a shortest program p which prints a string y such that d(x, y) ≤ a. We also study a conditional version of this measure Ca,b(x|y) where the task is, given a string y ′ such that d(y, y ′ ) ≤ b, print a string x ′ such that d(x, x ′ ) ≤ a. This definition admits both a uniform measure, where the same program should work given any y ′ such that d(y, y ′ ) ≤ b, and a nonuniform measure, where we take the length of a program for the worst case y ′. We study the relation of these measures in the case where d is Hamming distance, and show an example where the uniform measure is exponentially larger than the nonuniform one. We also show an example where symmetry of information does not hold for complexity with error under either notion of conditional complexity. 1