Time-Bounded Kolmogorov Complexity and Solovay Functions
Merkle · 2009
A Solovay function is a computable upper bound g for prefix- free Kolmogorov complexity K that is nontrivial in the sense that g agrees with K, up to some additive constant, on infinitely many places n .W e obtain natural examples of Solovay functions by showing that for some constant c0 and all computable functions t such that c0n ≤ t(n), the time-bounded version K t of K is a Solovay function. By unifying results of Bienvenu and Downey and of Miller, we show that a right-computable upper bound g of K is a Solovay function if and only if Ωg is Martin-Lrandom. Letting Ωg = 2 �g(n) ,w e obtain as a corollary that the Martin-Lrandomness of the various variants of Chaitin's Ω extends to the time-bounded case in so far as ΩKt is Martin- Lrandom for any t as above. As a step in the direction of a characterization of K-triviality in terms of jump-traceability, we demonstrate that a set A is K-trivial if and only if A is O(g(n) − K(n))-jump traceable for all Solovay functions g ,w here the equivalence remains true when we restrict attention to functions g of the form K t , either for a single or all functions t as above. Finally, we investigate the plain Kolmogorov complexity C and its time-bounded variant C t of initial segments of computably enumerable sets. Our main theorem here is a dichotomy similar to Kummer's gap the- orem and asserts that every high c.e. Turing degree contains a c.e. set B such that for any computable function t there is a constant ct > 0s uch that for all m it holds that C t (B m) ≥ ct ·m, whereas for any nonhigh c.e. set A there is a computable time bound t and a constant c such that for infinitely many m it holds that C t (A m) ≤ log m + c. By similar methods it can be shown that any high degree contains a set B such that C t (B m) ≥ + m/4. The constructed sets B have low unbounded but high time-bounded Kolmogorov complexity, and accordingly we obtain an alternative proof of the result due to Juedes, Lathrop, and Lutz (JLL) that every high degree contains a strongly deep set.