Time-bounded Kolmogorov complexity and Solovay functions - Hölzl, Rupert; Kräling, Thorsten; Merkle, Wolfgang (Theory of computing systems, 2013)
A Solovay function is an 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. We obtain natural examples of computable Solovay functions by showing that for some constant c0 and all computable functions t such that c0n≤t(n), the time-bounded version Ktof K is a Solovay function.