Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Kleene's realizability:
TR01-088 | 29th October 2001
Alexander Shen, Nikolay Vereshchagin

Logical operations and Kolmogorov complexity

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

TR01-089 | 29th October 2001
Andrej Muchnik, Nikolay Vereshchagin

Logical operations and Kolmogorov complexity. II

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

ISSN 1433-8092 | Imprint