An excursion to the Kolmogorov random strings

We study the set of resource bounded Kolmogorov random strings: R _t={x|K^t(x)⩾|x|} for t a time constructible function such that t(n)⩾2(n²) and t(n)∈2(nO(1)). We show that the class of sets that Turing reduce to R_t has measure 0 in EXP with respect to the resource-bounded measure introduced by Lutz (1992). From this we conclude that R_t is not Turing-complete for EXP. This contrasts the resource unbounded setting. There R is Turing-complete for co-RE. We show that the class of sets to which R_t bounded truthable reduces, has p₂-measure 0 (therefore, measure 0 in EXP). This answers an open question of Lutz, giving a natural example of a language that is not weakly-complete for EXP and that reduces to a measure 0 class in EXP. It follows that the sets that are ⩽_btt^p-hard for EXP have p₂ -measure 0