Resource Bounded Randomness and Weakly Complete Problems
Klaus Ambos-Spies, Sebastiaan A. Terwijn, Zheng Xizhong
Abstract:
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.