ECCC-Report TR01-089https://eccc.weizmann.ac.il/report/2001/089Comments and Revisions published for TR01-089en-usWed, 28 Nov 2001 16:40:13 +0200
Paper TR01-089
| Logical operations and Kolmogorov complexity. II |
Andrej Muchnik,
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/2001/089We 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)).
Wed, 28 Nov 2001 16:40:13 +0200https://eccc.weizmann.ac.il/report/2001/089