Resource Bounded Randomness and Weakly Complete Problems
Klaus AmbosSpies, Sebastiaan A. Terwijn, Xizhong Zheng
We introduce and study resource bounded random sets based on Lutz's
concept of resource bounded measure. We concentrate on n^crandomness
(c >= 2) which corresponds to the polynomial time bounded (p)measure
of Lutz, and which is adequate for studying the internal and
quantitative structure of E = DTIME(2^lin). However we will also comment
on E_2 = DTIME(2^pol) and its corresponding (p_2)measure. First
we show that the class of n^crandom sets has pmeasure 1. This provides
a new, simplified approach to pmeasure 1results. Next we compare
randomness with genericity, and we show that n^(c+1)random sets are
n^cgeneric, whereas the converse fails. From the former
we conclude that n^crandom sets are not pbttcomplete for E. Our technical
main results describe the distribution of the n^crandom sets under
pmreducibility. We show that every n^crandom set in E has n^krandom
predecessors in E for any k >= 1, whereas the amount of randomness of the
successors is bounded. We apply this result to answer a question raised by
Lutz: We show that the class of weakly complete sets has measure 1 in E and
that there are weakly complete problems which are not pbttcomplete for E.