Measure on small complexity classes, with applications for BPP
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (4) , 807-818
- https://doi.org/10.1109/sfcs.1994.365713
Abstract
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 /spl epsiv/>0, almost every set in E/sub /spl epsiv// is hard for BPP, where E/sub /spl epsiv//=/spl cup//sub /spl delta/Keywords
This publication has 17 references indexed in Scilit:
- The complexity and distribution of hard problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Relative to a random oracle, NP is not smallPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A Pseudorandom Oracle Characterization of ${\text{BPP}}$SIAM Journal on Computing, 1993
- Almost everywhere high nonuniform complexityJournal of Computer and System Sciences, 1992
- Self-reducibilityJournal of Computer and System Sciences, 1990
- Category and Measure in Complexity ClassesSIAM Journal on Computing, 1990
- Pseudorandom sources for BPPJournal of Computer and System Sciences, 1990
- On sparse oracles separating feasible complexity classesInformation Processing Letters, 1988
- Computation times of NP sets of different densitiesTheoretical Computer Science, 1984
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981