On total conditional complexity

Arseniy Savin
Moscow

Abstract.

It is well known that there are objects x any y such that Kolmogorov complexity of x conditional to y is much smaller than total conditional complexity of x given y. Such objects are usually constructed by diagonal arguments. We present natural examples of such objects x and y.