Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-058 | 25th September 2002 00:00

A generalization of Lutz's measure to probabilistic classes

RSS-Feed




TR02-058
Authors: Philippe Moser
Publication: 10th October 2002 18:49
Downloads: 2461
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