Conditional complexity and codes

AbstractLet x and y be binary strings. We prove that there exists a program p of size about K(x|y) that maps y to x and has small complexity when x is known (K(p|x)≈0). Having in mind the parallelism between Shannon information theory and algorithmic information theory, one can say that this result is parallel to Wolf–Slepian and Körner–Csiszar–Marton theorems, see (I. Csiszar and J. Körner, Information theory, Coding Theorems for Discrete Memoryless Systems, Akadémiai Kiadó, Budapest, 1981).We show also that for any three strings x,y,z of length at most n the length of the shortest program p that maps both y and z to x (i.e., p(y)=p(z)=x) equals max(K(x|y),K(x|z)+O(logn)