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-088 | 29th October 2001 00:00

Logical operations and Kolmogorov complexity

RSS-Feed




TR01-088
Authors: Alexander Shen, Nikolay Vereshchagin
Publication: 28th November 2001 16:40
Downloads: 2182
Keywords: 


Abstract:

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,
(A --> B) is the set of programs mapping
any element of A to an element of B.
We find complexity of certain
particular sets obtained from singelton sets (e.g. ({x}-->{y})-->{y}).




ISSN 1433-8092 | Imprint