Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-089 | 29th October 2001 00:00

Logical operations and Kolmogorov complexity. II

RSS-Feed




TR01-089
Authors: Andrej Muchnik, Nikolay Vereshchagin
Publication: 28th November 2001 16:40
Downloads: 1985
Keywords: 


Abstract:

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)).



ISSN 1433-8092 | Imprint