An Excursion to the Kolmogorov Random Strings

摘要

We study the sets of resource-bounded Kolmogorov random strings:Rt={x|Ct(n)(x)⩾|x|} fort(n)=2nk. We show that the class of sets that Turing reduce toRthas measure 0 inEXPwith respect to the resource-bounded measure introduced by Lutz. From this we conclude thatRtis not Turing-complete forEXP. This contrasts with the resource-unbounded setting. ThereRis Turing-complete forco-RE. We show that the class of sets to whichRtbounded truth-table reduces, hasp2-measure 0 (therefore, measure 0 inEXP). This answers an open question of Lutz, giving a natural example of a language that is not weakly complete forEXPand that reduces to a measure 0 class inEXP. It follows that the sets that are ⩽pbbt-hard forEXPhavep2-measure 0.