, 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
Plain stopping time and conditional complexities revisited, 2017. ,
URL : https://hal.archives-ouvertes.fr/lirmm-01803546
Stopping time complexity, abstract. Dagstuhl Reports, Computability Theory, Dagstuhl Seminar 17081, p.97, 2017. ,
Algorithmic complexity bounds on future prediction errors. Information and Computation, vol.205, pp.242-261, 2007. ,
Game interpretation of Kolmogorov complexity. CoRR, abs/1003, vol.4712, 2010. ,
Algorithmic variants of the notion of entropy, Soviet Mathematics Doklady, vol.29, issue.3, pp.569-573, 1984. ,
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
Kolmogorov complexity and algorithmic randomness, Mathematical Surveys and Monographs. American Mathematical Society, vol.220, 2017. ,
URL : https://hal.archives-ouvertes.fr/lirmm-01803620
Relations between varieties of Kolmogorov complexities, Mathematical Systems Theory, vol.29, issue.3, pp.271-292, 1996. ,
Universal probability-free conformal prediction, Conformal and Probabilistic Prediction with Applications, pp.40-47, 2016. ,