DIMACS TR: 94-18

Measure on Small Complexity Classes, with application for BPP

Authors: Eric Allender and Martin Strauss


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