We present a notion of resource-bounded measure for P and othersubexponential-time classes. This generalization is based on Lutz'snotion of measure, but overcomes the limitations that cause Lutz'sdefinitions to apply only to classes at least as large as E. Wepresent many of the basic properties of this measure, and use it toexplore the class of sets that are hard for BPP.

Bennett and Gill showed that almost all sets are hard for BPP; Lutz improved this from Lebesgue measure tomeasure on ESPACE.We use our measure to improve this still further, showing that forall epsilon > 0, almost every set in E_epsilon is hardfor BPP, where E_epsilon =the union over all delta < epsilon} of DTIME}(2^{n^{delta}}), which is thebest that can be achieved without showing that BPP is properly containedin E. A number of related results are also obtained in this way