__
TR02-058 | 25th September 2002 00:00
__

#### A generalization of Lutz's measure to probabilistic classes

**Abstract:**
We extend Lutz's measure to probabilistic classes, and obtain notions of measure on probabilistic complexity classes

C

such as BPP , BPE and BPEXP. Unlike former attempts,

all our measure notions satisfy all three Lutz's measure axioms, that is

every singleton {L} has measure zero in C, the whole space C has measure one in C,

and "easy infinite unions" of measure zero sets

have measure zero.

Finally we prove a conditional time hierarchy Theorem for probabilistic classes,

and show that under the same assumption,

both the class of $\leq^{p}_{T}$-autoreducible sets

and the class of $\leq^{p}_{T}$-complete sets for EXP have measure

zero in BPE.