Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles The Journal of Symbolic Logic Year : 2014

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

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|).
Fichier principal
Vignette du fichier
1202.6668.pdf (202.61 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00853082 , version 1 (20-04-2019)

Identifiers

Cite

Bruno Bauwens, Alexander Shen. Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity. The Journal of Symbolic Logic, 2014, 79 (02), pp.620-632. ⟨10.1017/jsl.2014.15⟩. ⟨lirmm-00853082⟩
179 View
89 Download

Altmetric

Share

More