1. We present a notion of resource-bounded measure for P and other subexponential-time classes. This is a generalization of Lutz's notion of measure, but Lutz's definitions apply only to classes at least as large as E, and several obstacles needed to be overcome to give a meaningful notion of measure for smaller classes. We present some of the basic properties of this measure; for example, forall k, DTIME(n^k) is a measure 0 subset of P.
2. We use this new notion of measure to show that for all epsilon > 0
almost every set A in the subexponential class E_epsilon is hard
for BPP, where
E_epsilon is the union of all delta < epsilon of DTIME(2^{n^delta}). This
is best possible without improving the known bounds on the deterministic
time complexity of sets in BPP.
Using similar techniques, we show that almost every set A in PSPACE
also satisfies this property. (This exponentially improves on the result of
[Lutz] showing that almost every set in ESPACE satisfies this
property.)
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-18.ps
DIMACS Home Page