- Author: D. van Melkebeek.
- Reference: Theoretical Computer Science, 244(1-2): 283-288,
2000.
Abstract
We show that BPP has p-measure zero if and only if BPP differs from
EXP. The same holds when we replace BPP by any complexity class
C that is contained in BPP and is closed under tt-reductions. The
zero-one law for each of these classes C follows: Within
EXP, C has either measure zero or else measure one.
