Logical operations and Kolmogorov complexity

AbstractConditional 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 (∧,∨,↔) 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