Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR02-058 | 25th September 2002 00:00

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

TR02-058
Authors: Philippe Moser
Publication: 10th October 2002 18:49
Keywords:

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.

ISSN 1433-8092 | Imprint