ECCC-Report TR04-080https://eccc.weizmann.ac.il/report/2004/080Comments and Revisions published for TR04-080en-usFri, 17 Sep 2004 20:57:35 +0300
Paper TR04-080
| Kolmogorov Complexity with Error |
Lance Fortnow,
Troy Lee,
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/2004/080We 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.
Fri, 17 Sep 2004 20:57:35 +0300https://eccc.weizmann.ac.il/report/2004/080