Alexander Shen, Nikolay Vereshchagin

We define Kolmogorov complexity of a set of strings as the minimal

Kolmogorov complexity of its element. Consider three logical

operations on sets going back to Kolmogorov

and Kleene:

(A OR B) is the direct sum of A,B,

(A AND B) is the cartesian product of A,B,

more >>>

Andrej Muchnik, Nikolay Vereshchagin

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