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