TR01-089 Authors: Andrej Muchnik, Nikolay Vereshchagin

Publication: 28th November 2001 16:40

Downloads: 2015

Keywords:

We invistigate what is the minimal length of

a program mapping A to B and at the same time

mapping C to D (where A,B,C,D are binary strings). We prove that

it cannot be expressed

in terms of Kolmogorv complexity of A,B,C,D, their pairs (A,B), (A,C),

..., their triples (A,B,C), (A,B,D), ..., and the quadruple (A,B,C,D)

up to an additive term of O(K(A,B,C,D)).