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.