Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR94-004 | 12th December 1994 00:00

Measure on Small Complexity Classes, with Applications for BPP


Authors: Eric Allender, Martin Strauss
Publication: 12th December 1994 00:00
Downloads: 1215


We present a notion of resource-bounded measure for P and other
subexponential-time classes. This generalization is based on Lutz's
notion of measure, but overcomes the limitations that cause Lutz's
definitions to apply only to classes at least as large as E. We
present many of the basic properties of this measure, and use it to
explore 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 to
measure on ESPACE.
We use our measure to improve this still further, showing that for
all epsilon > 0, almost every set in E_epsilon is hard
for BPP, where E_epsilon =
the union over all delta < epsilon} of DTIME}(2^{n^{delta}}), which is the
best that can be achieved without showing that BPP is properly contained
in E. A number of related results are also obtained in this way.

ISSN 1433-8092 | Imprint