Compressibility of Infinite Binary Sequences

It is known that infinite binary sequences of constant Kolmogorov complexityare exactly the recursive ones. Such a kind of statement no longer holds in thepresence of resource bounds. Contrary to what intuition might suggest, there are sequencesof constant, polynomial-time bounded Kolmogorov complexity that are notpolynomial-time computable. This motivates the study of several resource-boundedvariants in search for a characterization, similar in spirit, of the polynomial-timecomputable...