ECCC-Report TR02-058https://eccc.weizmann.ac.il/report/2002/058Comments and Revisions published for TR02-058en-usThu, 10 Oct 2002 18:49:26 +0200
Paper TR02-058
| A generalization of Lutz's measure to probabilistic classes |
Philippe Moser
https://eccc.weizmann.ac.il/report/2002/058 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.
Thu, 10 Oct 2002 18:49:26 +0200https://eccc.weizmann.ac.il/report/2002/058