Logical operations and Kolmogorov complexity
Conditional Kolmogorov complexity K(x/y) can be understood as the complexity of the problem " Y --> X", where X is the problem "construct x" and Y is the problem "construct y". Other logical operations (boolean AND,boolean OR, ) can be interpreted in a similar way, extending Kolmogorov interpretation of intuitionistic logic and Kleene realizability. This leads to interesting problems in algorithmic information theory. Some of these questions are discussed. (C) 2002 Elsevier Science B.V. All rights reserved.
kolmogorov complexity intuitionistic logic realizability