Time-Bounded Kolmogorov Complexity and Solovay Functions
A Solovay function is an upper boundg for prefix-free Kolmogorov complexityK that is nontrivial in the sense thatg agrees withK, up to some additive constant, on infinitely many placesn. We obtain natural examples of computable Solovay functions by showing that for some constantc 0 and all computable functionst such thatc 0 n?t(n), the time-bounded versionK t ofK is a Solovay function.
kolmogorov complexity solovay function computational depth kummers gap theorem traceability high degree