, The factor 2 that appears in the previous statement is optimal: if K is a function in the class (for example, the minimal one), then C(x | y * ) ? 2K(x, y) + c for some c and for all x and

M. Andreev, G. Posobin, and A. Shen, Plain stopping time and conditional complexities revisited, 2017.
URL : https://hal.archives-ouvertes.fr/lirmm-01803546

M. Andreev, G. Posobin, and A. Shen, Stopping time complexity, abstract. Dagstuhl Reports, Computability Theory, Dagstuhl Seminar 17081, p.97, 2017.

A. V. Chernov, M. Hutter, and J. Schmidhuber, Algorithmic complexity bounds on future prediction errors. Information and Computation, vol.205, pp.242-261, 2007.

A. A. Muchnik, I. Mezhirov, A. Shen, and N. Vereshchagin, Game interpretation of Kolmogorov complexity. CoRR, abs/1003, vol.4712, 2010.

A. Shen, Algorithmic variants of the notion of entropy, Soviet Mathematics Doklady, vol.29, issue.3, pp.569-573, 1984.

A. Shen, Around Kolmogorov complexity: Basic notions and results, Measures of Complexity: Festschrift for Alexey Chervonenkis, pp.75-116, 2015.
URL : https://hal.archives-ouvertes.fr/lirmm-01233758

A. Shen, V. A. Uspensky, and N. Vereshchagin, Kolmogorov complexity and algorithmic randomness, Mathematical Surveys and Monographs. American Mathematical Society, vol.220, 2017.
URL : https://hal.archives-ouvertes.fr/lirmm-01803620

A. Vladimir, A. Uspensky, and . Shen, Relations between varieties of Kolmogorov complexities, Mathematical Systems Theory, vol.29, issue.3, pp.271-292, 1996.

V. Vovk and D. Pavlovic, Universal probability-free conformal prediction, Conformal and Probabilistic Prediction with Applications, pp.40-47, 2016.