Total conditional complexity of certain objects

The fine approach to measure information dependence is based on the total conditional complexity CT ( y | x ), which is defined as the minimal length of a total program that outputs y on the input x. It is known that the total conditional complexity can be much larger than the plain conditional complexity. Such strings x, y are defined by means of a diagonal argument and are not otherwise interesting. In this paper we investigate whether this happens also for some natural objects having some other interesting properties. More specifically, we consider the following objects: the number of strings of complexity less than n and the lex first string of length n and complexity ⩾n. It is known that they have negligible mutual conditional complexities. In this paper we prove that their mutual total conditional complexities may be large. This is the first example of interesting objects whose plain conditional complexity is much less than the total one.

Authors

• Nikolay Vereshchagin

Keywords

• Kolmogorov complexity
• Algorithmic information theory
• Total conditional complexity