The Zero-One Law Holds for BPP Download as PS


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.