TR04-080 Authors: Lance Fortnow, Troy Lee, Nikolay Vereshchagin

Publication: 17th September 2004 20:57

Downloads: 3215

Keywords:

We introduce the study of Kolmogorov complexity with error. For a

metric d, we define C_a(x) to be the length of a shortest

program p which prints a string y such that d(x,y) \le a. We

also study a conditional version of this measure C_{a,b}(x|y)

where the task is, given a string y' such that d(y,y') \le b,

print a string x' such that d(x,x') \le a. This definition

admits both a uniform, the {\em same} program should work given

any y' such that d(y,y') \le b, and nonuniform measures, 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.