Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity

Bruno Bauwens 1 Alexander Shen 2
2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Peter Gacs showed (Gacs 1974) that for every n there exists a bit string x of length n whose plain complexity C(x) has almost maximal conditional complexity relative to x, i.e., C(C(x)|x) > log n - log^(2) n - O(1). (Here log^(2) i = log log i.) Following Elena Kalinina (Kalinina 2011), we provide a simple game-based proof of this result; modifying her argument, we get a better (and tight) bound log n - O(1). We also show the same bound for prefix-free complexity. Robert Solovay showed (Solovay 1975) that infinitely many strings x have maximal plain complexity but not maximal prefix complexity (among the strings of the same length): for some c there exist infinitely many x such that |x| - C(x) < c and |x| + K(|x|) - K(x) > log^(2) |x| - c log^(3) |x|. In fact, the results of Solovay and Gacs are closely related. Using the result above, we provide a short proof for Solovay's result. We also generalize it by showing that for some c and for all n there are strings x of length n with n - C (x) < c and n + K(n) - K(x) > K(K(n)|n) - 3 K(K(K(n)|n)|n) - c. We also prove a close upper bound K(K(n)|n) + O(1). Finally, we provide a direct game proof for Joseph Miller's generalization (Miller 2006) of the same Solovay's theorem: if a co-enumerable set (a set with c.e. complement) contains for every length a string of this length, then it contains infinitely many strings x such that |x| + K(|x|) - K(x) > log^(2) |x| + O(log^(3) |x|).
Type de document :
Article dans une revue
The Journal of Symbolic Logic, Association for Symbolic Logic, 2014, 79 (02), pp.620-632. 〈10.1017/jsl.2014.15〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00853082
Contributeur : Alexander Shen <>
Soumis le : mercredi 21 août 2013 - 17:56:14
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Lien texte intégral

Identifiants

Citation

Bruno Bauwens, Alexander Shen. Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity. The Journal of Symbolic Logic, Association for Symbolic Logic, 2014, 79 (02), pp.620-632. 〈10.1017/jsl.2014.15〉. 〈lirmm-00853082〉

Partager

Métriques

Consultations de la notice

146