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.