Résumé
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 (
∧,∨,↔) 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.