In this paper we construct a structure R that is a “finite version” of the semi-lattice of Turing degrees. Its elements are strings (technically, sequences of strings) and x `<=` y means that K(x|y)=(conditional Kolmogorov complexity of x relative to y) is small. We construct two elements in R that do not have greatest lower bound. We give a series of examples that show how natural algebraic constructions give two elements that have lower bound 0 (minimal element) but significant mutual information. (A first example of that kind was constructed by Gács–Körner(Problems Control Inform. Theory 2 (1973) 149) using a completely different technique.) Wede4ne a notion of “complexity profile” of the pair of elements of R and give (exact) upper andlower bounds for it in a particular case.
- Kolmogorov complexity
- common information
- conditional complexity
Chernov, A., Muchnik, A., Romashchenko, A., Shen, A., & Vereshchagin, N. (2002). Upper semi-lattice of binary strings with the relation "x is simple conditional to y". Theoretical Computer Science, 271(1-2), 69-95. https://doi.org/10.1016/S0304-3975(01)00032-9