Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-080 | 7th September 2004 00:00

Kolmogorov Complexity with Error


Authors: Lance Fortnow, Troy Lee, Nikolay Vereshchagin
Publication: 17th September 2004 20:57
Downloads: 1239


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.

ISSN 1433-8092 | Imprint