## DIMACS TR: 94-18

## Measure on Small Complexity Classes, with application for BPP

### Authors: Eric Allender and Martin Strauss

**
ABSTRACT
**

The main contributions of this work are:
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