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 c...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 1997-06, Vol.54 (3), p.393-399
Main Authors: Buhrman, Harry, Mayordomo, Elvira
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0022-0000
1090-2724
DOI:10.1006/jcss.1997.1484